15

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?

2
  • 1
    It boils down to the existence of mathematical operations that are easy in on direction but difficult in another. For example multiplying 167 and 173 will result easily in 28891. But if I tell you 17063 and ask you for the two factors, it is quite difficult to get to 151 * 113. Of course this is an example for humans, the numbers need to be much larger for computers Sep 24, 2011 at 7:41
  • 2
    To add to what Hendrik says, the wikipedia article for RSA contains some nice examples and info. The longest number factored in 2010 was 768 bits; RSA keys are 1024 or 2048 (or larger) bits. The product of two 2048 bit keys is a 4096 bit number; that's about 1234 digits long.
    – DanBeale
    Sep 24, 2011 at 17:09

5 Answers 5

16

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.

2
  • Hi Jeff, thanks for your answer. I wanted to see the demo at "people.eku.edu/styere/Encrypt/RSAdemo.html" but unfortunately it's not available anymore. Is there a change to find it at a different URL? Thanks
    – Vojta
    Oct 31, 2022 at 13:46
  • The demo link seems not to work.
    – john-jones
    Mar 13 at 12:50
7

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.

6

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.

5

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.

2
  • 2
    so the Modulus is also a large prime number? and what do you have to choose the private key to be?
    – Vass
    Jan 26, 2015 at 22:19
  • How does that work? Doesn't a modulus operation lose data so that it's impossible to recreate the original? That is, 8 % 5 = 3 but so does 13 % 5 = 3, so there's no way to know which one resulted in the answer of 3.
    – Simon East
    May 16, 2017 at 9:11
3

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

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

1
  • Guess, a message is already encrypted, when it sees this Pearl fragment :) Jan 9, 2022 at 9:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .