I'm doing a project where I need to either find or build an RSA and an Elgamal algorithm, a triple DES algorithm, and a digital hashing signature algorithm.
I'm trying to put my code together, but I keep getting hung up on coding RSA and Elgamal. I was wondering if anyone had any useful links to RSA pseudocode: specifically, calculating large primes (aka p and q) [I can't seem to get euler's right], and finding a coprime to phi(n) = (p-1)(q-1) (aka e). The purpose of all of the equations I'm trying to code is to find large primes, efficiently. If anyone knows of an easier way to do this [calculating large primes efficiently], it would be greatly appreciated.
Additionally, I'm getting a little hung up on padding... I can scrape by with my project just doing a nonpadded encryption/decryption, but I want to kind of go above and beyond... any links to useful padding schemes/padding scheme pseudocode would be greatly helpful.
I tried searching on google for good pseudocode, but I've only really found kind of ambiguous pseudocode for the large prime calculation... (either that or I'm just really dense).
Any help would be greatly appreciated (and just to specify, I don't need someone to write an entire algorithm for me, I just need a push in the right direction).
Thank you for your time.
I'm trying to put my code together, but I keep getting hung up on coding RSA and Elgamal. I was wondering if anyone had any useful links to RSA pseudocode: specifically, calculating large primes (aka p and q) [I can't seem to get euler's right], and finding a coprime to phi(n) = (p-1)(q-1) (aka e)
Generating large primes isn't easy, since no proper way to calculate a prime is known (luckily, if there was one, RSA would be broken). What you normally do is take random numbers and perform a primality test like Miller-Rabine which preforms very well (50 executes narrows it down to a 1/2^50 percent chance that the tested number is a prime). The only requirement is that the random numbers have to be really really random, else the found key is not safe. Linux /dev/random is a good source to initiate a random generator. Or the preferred crypto module of a language (C: openssl, Java: SecureRandom...).
There is no real pseudocode around RSA, since it is a mathematical process. The closest to pseudocode I could get was a python implementation For prime generation there is a neat python example on literate programs. Also here
About padding, wikipedia explaines one padding scheme pretty well. Also this blog entry helped me a lot understanding padding. Links about padding: http://rdist.root.org/2009/10/06/why-rsa-encryption-padding-is-critical/ http://www.symantec.com/connect/blogs/common-rsa-implementation-mistake-explained
I hope this pushes you into the right direction.