Projects and Sources


Big number factoring using parallel GNFS (In Spanish-Undergrad thesis)
Implementation of a Boinc volunteer grid computing environment in the university campus to factor RSA-100 and RSA-110 using the GNFS algorithm. Co-author Ivan Rey.

Design of a redundant descentralized backup system for LANs, it employs: threshold schemes for key redundancy, Simmetric cryptographic primitives, Rivest's all or nothing transformation and Rabin's Information Dispersal Algorithm (see implementation below in Cryptography section).

A protocol for guaranteeing privacy in emails stored at locations that could be compromised such as web based e-mail services.

A method for using CDMA in cryptosystems with additive homomorphisms. Co-Author: Jaime Posada.

A method for load balancing in the crowds anonymous network using Ring Signatures and Linkable Democratic Group Signatures.   Co-Author: Jaime Posada.

An effective descentralized, low cost cryptographic alternative to methods implemented in Colombia to control the express kidnappings in taxis occurring in major colombian cities. 

A cache system using pieces of shared information as its source of information using a suffix tree for quick access.

Source Code

This is the source code section, effort has been done to write standalone implementations compatible with standard compiler distributions, in this way it is easier to incorporate the source code to an existing application and play around with the algorithms. Unless otherwise stated the source files are written in Java (jdk 6.0). 

I'm releasing all the source codes under BSD license , if the code is to be used in a commercial application check that there are no patents regarding the algorithms, the implementations are made for educational purposes. Special care needs to be taken specially with the Cryptographic algorithms, since they have not been tested against all possible attacks.

Email me if there are any comments, bugs, improvements or anything regarding the sources.


Public Key Algorithms

I find public key algorithms a fascinating topic, it is one of those fantastic things in Cryptography seeming to defy common sense. Eventhough there are many of them in the literature, it is not common to see a real world implementation with algorithms other than RSA. In this section you can find the algorithms I've worked with for some reason.

Classes in this section have a constructor generating keys, a constructor for encryption, a constructor for encrypting and decrypting, an encrypt method and a decrypt method. The idea of such coding strategy is to use the same class for every instance in a real world application; also all the codes include a main method showing how to use the class and some of them show the homomorphic properties of the algorithm.

Benaloh: An extension of Goldwasser-Micali, it has additive homomorphism too, there are some cryptographic voting systems using it. Co-author: Jaime Posada.
Diffie-Hellman: Well this isn't exactly for encryption but they started the public key idea. In this code there are methods to generate the parameters p and g, since it is slow for 1024, generate p and g, store them somewhere and use them as a public parameters in the system. 
Goldwasser-Micali: The first probabilistic encryption scheme, encrypts bit by bit, it uses quadratic residues.
Paillier: Algorithm with additive homomorphism, very popular for cryptographic voting systems. Co-author: Jaime Posada.
Rabin: Algorithm based on the integer factorization problem, the encryption function is very simple and has other nice properties for oblivious transfer.
RSA: The first true public encryption scheme, there are many implementations around but here is another one.

Identity Based Encryption

Identity Based Encryption has very appealing properties for some environments, unlike traditional public key infrastructures where there is a chain of certificates issued by certification authorities, in IBE schemes the public key for an individual is derived from its identity, to get the private key corresponding to that identity, one must go with the Public Key Generator (PKG) who can compute private keys.

Most of the IBE schemes out there use elliptic curve pairings,  I'm working in implementing those schemes, in the menatime here is one algorithm based in number theory.

Cocks-IBE: An IBE scheme based on Quadratic Residues, it is very inefficient in space.

Digital Signatures

DSA: The digital signature algorithm, the code lets  change the parameters for p,q and the hash function. There are four constructors for the possible usage scenarios, parameter generation is kinda slow for 1024 bits, please be patient when running the code.

Threshold Schemes

Threshold schemes allow to share responsibility for storing or computing a function, they depend on two values, one of them is the number of entities involved and the other is how many entities are needed to compute a function or reveal a secret.

Shamir's secret sharing scheme: It uses polynomial interpolation to split a secret among several parties, the code uses Gauss-Jordan in Zp to recover the secret.

Zero Knowledge Proofs

In zero knowledge proofs one entity called the prover,  proves to an entity called the verifier the knowledge of a secret without actually telling the secret, there are interactive and non-interactive protocols. For the interactive protocols steps are numbered for prover and verifier in the source code, for the non interactive ones there are two methods only: prove and verify.

Feige-Fiat-Shamir: In this interactive protocol there is a public parameter n. The prover wishes to prove the knowledge of the modular square roots (s) of an array (v) known to the verifier.
Equallity two discrete logarithms
Modular square root

Information Dispersal Algorithms

Information Dispersal Algorithms, allow to split a file in n slices, from those n slices any k (k<n) slices suffice to reconstruct the original file. Parameters n and k can be given at split time.

Rabin-IDA: The algorithm proposed by Rabin, it is optimal in terms of information overhead. For a L length file, splitted in n pieces where k suffice for reconstruction, the size of each slice is L/k. The implementation uses arithmetic in GF(2^8) and Vandermonde matrices. I wish to thank Alejandro Sotelo for the help given in finite field arithmetic and his code for inverting Vandermonde matrices in quadratic time. The code can be downloaded as a zipped Visual C++ 2008 express project. For usage instructions read the main file.