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

  • 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?

    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

    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.

  • 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.

License under CC-BY-SA with attribution


Content dated before 7/24/2021 11:53 AM