Programs and Criptography Stuff

DISCLAIMER: Whatever source, executable or any other data from this page and the whole website is given "as is", with no warranty whatsoever. I am an amateur coder, so please bear in mind that each and any of my programs are likely to contain bugs, which I may either be aware of or not, with no implied committment from my side to correct them even if you notify me. By browsing or downloading this page you agree that no damage, direct or indirect, due to the use of any software or information from this page, can be claimed on me.

beamformer

This is a crude set of a few MATLAB functions useful for simulating the beamforming cabability of arrays of isotropic sources or receivers in a homogeneous medium. Indeed, they are geophones in my head, but the physics would work with any other receiver similar, or source of course. The whole thing is meant primarily for my use and fun in numerically explore the basic concepts of beamforming "hands-on". Given the parameters for the array, the propagation medium, the (sinusoidal) signal of interest and a few settings, the top function plotgain calls symarray, which synthesises the samples track for each one of the array sensors by iteratively calling maketrack. The resulting tracks are added together (with constant unity weight) by arrayaddersimple and then the resulting amplitude gain vs. incoming angle for the whole array gets plotted on (half) a polar plot.

The above animation of a beam steering over 180° has been made with these functions, and the functions arguments are self explanatory in the source, so I won't write more here now. I am currently experimenting with a slightly rewritten revison which comprises the arrayadderweighted and arrayadderweightedt functions to allow other than unity weights and time-varying weights, but they are not yet in the downloadable package.
By the way... I am just playing and learning with this stuff in my spare time, so bear this in mind if you decide to try the code. Here it runs fine on MATLAB 7.0, but I believe it will run under older releases too.
Cheers...

itav2csv

This command line utility converts datafiles containing synoptical observatios by meteorological stations managed by the Meteorological Office of the Italian Air Forces into the .csv format understood by Excel and other spreadsheet software. The original input files look a bit puzzling:

...
070051013106 8650000-070-0807473 0      284                     0937
070051013109 8950000             0      032
070051013112 8950000             0      02
070051013115 8970000             0      03-
070051013118 8970000-062-0907472 0      032                     0817
070051020103 8900000             0      02-
07005102010698900000-074-0907487 0      020 00000090            0837
070051020109 8900000             0      020
07005102011298900000             0      020 00000090
070051020115 8900000             0      020
07005102011898900000-072-1107493 0      020 00000090            0777
...

In 2001 I needed meteorological information from the station located on the summit of Grigna Settentrionale, the mountain where I was working for my MSc thesis, and so I had to decode this file. Since format specifications were available, I could write two small command line programs named itav2csv.exe and separa.exe to perform the task. The executables were compiled with MS Visual C++ 6 and GNU djgpp, respectively (the reason being I was playing around with both). If you download the source files, please bear in mind this was one of my first hacks in C... which means that after years they are almost illegible to me too, and they are a bad mix of C and C++ elements. Also, VC++ resource files are not included due to the mess in my old backups, but the sources will still compile cleanely (re-tested now with VC++ 6)

itav2csv.exe is configurable and you have to supply it with a data_format_file telling exactely how your original data are formatted. For synoptic records from the Italian Air Forces Meteorological Office, you need the itav.txt file. itav2csv.exe and its preprocessor separa.exe are self explanatory, with sintax reminders being printed out when they are invoked without arguments. You have to first invoke separa.exe passing to it the original data file, and the output will be two new files, basicly containing synoptic and summary records. You will now invoke

itav2csv data_file [data_format_file]

to get your nicely formatted output, complete with column description in the first line. You may have noticed that data_format_file is an optional parameter, and the program will deafult to look for itav.txt Apart from this, please don't be rude with the command line arguments parser...

owaccu

This is a C++ implementation of the cryptografic one-way accumulators by Benaloh J.C. & de Mare M. (1993) - One-way Accumulators: A Decentralized Alternative to Digital Timestamps. Advances in Cryptography, Eurocrypt '93. Please refer to the original paper for background and theoretical information.

owaccu.cpp defines the owaccu class:

class owaccu {

	...
	
public:
	owaccu(int rigidprimedigits, int rigidprimebase, int participants);
	owaccu(Big modulus, Big agreedbase, Big accumulatedhash);
	~owaccu();
	Big add_member(member_data *member);
	member_data get_member_data(int member_number);
	int check_membership(member_data *member);
	Big get_accumulated_hash();
	Big get_agreed_base();
	Big get_rigid_prime();
};

containing the implementation of the cryptographic primitive, and
a struct member_data containing member's data.

struct member_data {
   char name[40];
   char passwd[40];
   Big z_k;
   member_data(){z_k = 0;};
};

While accumulating members, the class owaccu populates a private array of type member_data, whose memory is dinamically allocated at runtime based on the number of entries (int participants in the source) in the input members list. It has to do so because knowledge of the full list is required by the Benaloh & De Mare's algorithm during the computation of the accumulated hash. For the same reason it is not possible to add further members at a later time without either re-accumulating the whole list (old + new members) or by recovering some of the contents of this array of structures of type member_data, and specifically the Big z_k member variable. However, since z_k contains the member's credential, under most settings it may not be desirable (secure) to permanently store all of these values longer than needed (e.g., the leak of a z_k value would allow to prove the membership of that member without her own participation).
The demo and owa v.0.1 command line implementation don't deal explicitly with this issue since the whole owaccu object is destroied right after output of the results. Since the memory for the said array is dynamically allocated, it is necessary to free it upon destruction of the owaccu object. The ~owaccu() destructor takes care of this, so be sure it gets executed at some time, and it also attempts (naively) to overwrite a few times the corresponding memory locations. This should help against the attack technique described in ...

It is interesting to observe that no user can be dishontestly added once the member have their z_k credentials from the correct accumulation of the legitimate list.

Given h(x,y) = x^y mod n with n being a large "rigid prime", here is how the algorithms work:

members accumulation (decentralized model): Alice, Bob and Charles (each knowing the h(x,y) function, x, n and the names of the other 2 members) independently compute z = h(h(h(x, yAlice), yBob), yCharles), where yAlice = "Alice", yBob = "Bob" and yCharles = "Charles". Each of them stores the z_k resulting from accumulation of all the members but himself. Each member knows the identity of the other members (if the names are exchanged in clear).

members accumulation (centralized, "trusted authority" model): Trent knows the names of Alice, Bob and Charles, the h(x,y) function, x and n. He independently computes z = h(h(h(x, yAlice), yBob), yCharles), where yAlice = "Alice", yBob = "Bob" and yCharles = "Charles", and sends out to each member the respective z_k resulting from accumulation of all the members but himself. Trent knows the identity of all the members (if the names are exchanged in clear), and he may also add phony members.

membership testing (to another member): Alice asserts her membership to Bob by showing to him that h(z_Alice, yAlice) = z, and Bob verifies that she is actually a member since also h(z_Bob, yBob) = z. Alternatively, he may have stored z since the beginning.

membership testing (to a non-member): z has to have been published and Xavier knows it. Then, Alice proves her membership to Xavier by showing to him that h(z_Alice, yAlice) = z.

The actual implementation in the owaccu class is slightly more elaborate. Notably, each member's identity information is hashed using the standard NIST SHA1 algorithm to obtain the effective y used (please refer to the original paper for background and theoretical information). Notice that now the theoretical security of the whole scheme thus rests on two assumptions :

the RSA assumption is appropriate
the SHA1 one way hash is collision-free

The passwd string is simply strcat'ed with name before SHA1 in order to produce the identity information for one-way accumulation (it may be seen as a special case of "other desired identifying characteristics" referred to in the Benaloh & de Mare 1993 paper). Having such a private component in the member id information implies that:

in the trusted authority model, Trent needs to know each member's secret at accumulation time. If Trent is not trustworthy, or he gets somehow compromised during the process and he doesn't forget Alice's secret and z_Alice, he may later "prove" Alice's membership both to members and to non-members without her participation. However she can easily disclaim her membership since Trent could have secretly and dishonestly added her name right from the beginning. On the other hand, if Trent forgets the secrets, neither him nor any other member or non-member can prove to anybody that Alice is a member without her surrendering her secret. This holds true even if they happen to know her name and z_Alice credential. This is a notable property of Benaloh & de Mare one-way accumulators. This may also lower the storage required from each member, since at least in some settings the various z_Member values may be published and each user just needs to retain his password.
in the decentralized model, no significant practical advantage appears to be gained by the inclusion of secret information: each member must know any other member's secret when first accumulating all the members but himself to get his own z_k credential, and then he could forget (Bob) or keep (Charles) those secrets. Now Charles, who maliciously didn't forget Alice's secrets, may prove the membership of Alice to non-members without Alice's participation. This holds true for the decentralized approach with or without the secret data in the member id.

It must be noted that for denial to be credible, Alice should be able to pretend her z_k credential is from membership in a different "club". I suppose (I am not a professional cryptografer, remember?) this could be done by letting Alice know the factorization of n, but leakage of this information would in turn compromise the whole membership system.

To compile owaccu.cpp you will need Michael Scott's Miracl multiprecision math library (I used version 5), which defines the Big type. It is a very fast and easy to use library, but please check for licensing conditions (very favourable when you don't use it for commercial purposes!).

The owaccu.cpp and owaccu.h sources contains the implementation of the owaccu class; owaccudemo.cpp is the source for a simple demo, which clarifies how to use the owaccu class. With owaccudemo.cpp the option is given (in the form of a #define VERBOSE_OUTPUT directive) to build a demo application or even a verbose demo version, which are very useful for understanding the internal working of one-way accumulation and testing.
The last possibility is building the stand-alone command line application owa.exe from owa.cpp. owa v.0.1 is suitable to be operated either in the decentralized or secrets-forgetting trusted authority or secrets-remembering trusted authority model, with accumulation and membership testing capability of members with or without secrets, or even of mixed users (with and without secrets).
The accumulation part of the command line implementation should perform ok, while the membership checking is still in a somewhat hacked up form (it depends on the exact filenames and file formats output during the accumulation process, so that if you change the filenames it wil not work anymore. I will correct this when I'll got some spare time...
You can download this package (containing the source files, compiled win32 executables, the congress.txt sample users list and a sample output obtained using the last command line from this section). Try owa.exe by first accumulating the users in the congress.txt file using a 308 digits modulus (~1024 bits, it may take up to a few minutes to generate the rigid prime on an average 2005 pc):

owa -a congress.txt -d 308

You will find a number of new files, one for each member. Now try to check the membership of Chiara, whose secret is hiar:

owa -c Chiara_congress.txt -p hiar

You may also combine two operations in one program run, as in thi example, where we also ask for output of secrets in a separate file (as would be in implementing the secret-remembering trusted authority model):

owa -a congress.txt -d 308 -r -c Chiara_congress.txt -p hiar

In memoriam of my first PC

My first PC was a fantastic Olivetti M24. It had an Intel 8086 processor, 640 Kb of RAM, a 20 Mb HDD, two DS DD 5.25" floppy drivers and DOS 3.2. I never got a fastest PC, ever! Can you remember things like Lotus 1-2-3 and its macro laguage? Then, Windows came. I think part of the fun to me in using Linux is that it looks like a clever-ized DOS. I know it went the opposite direction with DOS and Unix, but I began on my M24, and DOS was there... Even so, games looked not so great on a green monochrome CRT (to me at least), thus I discovered how entertaining it was to hack around with BASICA.exe, an "amazing" thing coming for free with the OS! I think I've spent some thousands hours at that, and of course during the way I came up with a "super secure" stream cipher, which I was very pleased with until I discovered: a) some clever guys had got it way before; b) rnd is not so secure a prng...
Ok, a lot of time has passed but I still like these things, and I still miss my M24. I guess it is a rusty box in a dump area now, which I would consider to be a shame on those who got it second hand from me.

back to the home page
http://www.citterio.net/software/software_en.html was last updated on August 17, 2006.