Is there a simple example of an Asymmetric encryption/decryption routine?

Question

I can understand Java, Perl and JavaScript code very well. The rest, I have not studied, but I guess I could figure out how to read/translate.

I would like to know what the simplest of Asymmetric routines are. Is it really too complex to want to worry about?

I am just really curious how it is possible to have an encryption-only key! It just seems amazing to me that it could resist reverse-engineering so I want to know how it works!

1. Is it too complicated for that.
2. What is (one of) the simplest standard Asymmetric encryption routine(s) that I can look up an implementation for?
3. If you happen have any minimal code examples that would be nice.

I already checked the Wikipedia paragraphs on How It Works, but there was no mathematical breakdown or description of implementation, just lots of implementations. I did not really want to randomly pick which one to look at, neither did I want to take the most common one which I expect is most robust and most complicated.

Any thoughts?

Answer 1

As far as RSA goes, this provides a good example that can be followed and shows corresponding examples of input and output. This demo application will walk you through the various steps and allow you check the work. Sometimes just clicking your way through something in steps like that will help. For Wikipedia articles, you need to look at the actual algorithm article: RSA for the math that corresponds.

Implementation wise, you can pull this together clearly in Java in under 30 lines.

For your understanding, there is no such thing as an encryption-only key. Rather, there are two equal keys that reverse the operations of their partners. We arbitrarily assign one of the pair as private and one as public. Things encrypted with one key can be decrypted with the other key. This is the principle used with signing.

It is not an issue of anti-reverse engineering that makes the keys safe, but rather a mathematical concept that you can't reasonably check the massive keyspace (when the key uses a really large number space) to find the matching key. There's no real speed-up for factoring work.

There are other asymmetric key algorithms to learn, but as you're staring out I'd try understand RSA, the oldest and most common, first.

Answer 2

Credit goes to Jeff's answer for the details and Steve's answer which was also helpful. Credit also goes to tylerl's answer which included links to Wikipedia for all the functions, particularly modInverse, also it clarified the ambiguous starting point for e. Thank you, I upvoted your answers, and using combined information from all three answers, I created what I hope is a better answer.

The key to making reverse-engineering so expensive is using power-of. Square root is not so hard, power of 3 means you need a cubed root, but power of 34,051,489 is pretty hard. There are other mathematical operations that are difficult to reverse-engineer. There are also multiple ways to create an Asymmetric Algorithm, but this answer focuses on RSA. The oldest and most common.

RSA Algorithm (based on the Java Code)

The the below calculations should be done with arbitrary precision integers. (Such as BigInt or BigInteger)

Generating the keys:

• Constant key length is l.
• Usually constant e_start can =3 for simplicity. However, 0x10001 is more common, at any rate, a prime number is best (for key-generation performance reasons and probably other reasons).
• p and q are the randomly generated positive prime numbers, that require up to l bits for storage. (To keep these positive, the first bit will always be 0)
• n = p*q This is used for both the encryption and decryption.
• e starts off as e_start. This will eventually be the part of the encryption key.
• m = (p-1)*(q-1) is used to convert e to d, which will be used for decryption.
• while(gcd(e,m)>1){e+=2} This is necessary for the next step to work.
• d=modInverse(e,m) This performs a standard arithmatic operation. Probably not worth examining much, especially if your programming language has this built in

To encrypt or decrypt, first convert your bytes to a single arbitrary precision integer.

Encryption: encrypted=(plain^e)%n

Note: If plain>=n, you must split plain into two or more smaller values and encrypt them separately.

Decryption: plain=(encrypted^d)%n

Asymmetric encryption is typically less efficient than Symmetric encryption. Sometimes Asymmetric encryption is used only for key exchange.

Answer 3

I put together a demonstration of RSA using python (python is very easy to read even if you've never seen it before). The code is long enough that it doesn't fit on a single page, but short enough that you can read and understand it in a few minutes.

Since encryption/decryption can be accomplished in a single built-in command -- exp(PLAINTEXT,KEY,MODULUS) -- I also go through the whole key derivation process as well.

You'll find the code here: https://gist.github.com/1239116

When you run the code, it asks you to for input in the form of >12345 or <12345, where the > prefix tells it to apply private key to the number, while < tells it to apply the public key. In the interest of simplicity, it only encodes numbers; but once you have that, encoding arbitrary data is just a matter of formatting.

Answer 4

Actually, the math around it is pretty simple, as I understand it. You take a value to the power of a rediculously large prime number (thousands of digits) and do a mod from another number.

So to encrypt you have something like: EncryptedBits = (PlainText ^ YourPublicKey) % Modulus

And to decrypt you have something like: PlainText = (EncryptedBits ^ YourPrivateKey) % Modulus

I came across a pretty easy to read document on it here: http://mathaware.org/mam/06/Kaliski.pdf

I'm not sure about any libraries to look at though.

Answer 5

If you want a cute, minimal perl solution, there is a classic one by Adam Back from 1995:

• export-a-crypto-system sig

It was printed on a t-shirt, including a barcode to make it computer-readable, along with the statement "This T-shirt is a Munition". That statement was accurate in the US before strong cryptography was reclassified in 1996 to no longer technically be a "munition". But was still broadly illegal to export strong cryptography from the US until the Export Administration Regulations (EAR) were revised in 2000:

The software has also been distributed as a tattoo, email signature, mailing label, and in many other forms, and even appeared (in blurred form) in the New York Times (the article, without the photo, is online at Between a Hacker And a Hard Place). A more recent 2-line version is:

print pack"C*",split/\D+/,`echo "16iII*o\U@{$/=$z;[(pop,pop,unpack"H*",<>
)]}\EsMsKsN0[lN*1lK[d2%Sa2/d0<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<J]dsJxp"|dc`

Note that the original approach relies on the Unix "dc" program for arbitrary precision arithmetic. A pure-perl version, with annotation, is at

• RSA in 5 lines of perl