is this a correct way to generate rsa keys?

Question

is this code going to give me correct values for RSA keys (assuming that the other functions are correct)? im having trouble getting my program to decrypt properly, as in certain blocks are not decrypting properly

this is in python:

import random
def keygen(bits):
    p = q = 3
    while p == q:
        p = random.randint(2**(bits/2-2),2**(bits/2))
        q = random.randint(2**(bits/2-2),2**(bits/2))
        p += not(p&1)                             # changes the values from 
        q += not(q&1)                             # even to odd

        while MillerRabin(p) == False:            # checks for primality
            p -= 2
        while MillerRabin(q) == False:
            q -= 2
    n = p * q   
    tot = (p-1) * (q-1)
    e = tot
    while gcd(tot,e) != 1:
        e = random.randint(3,tot-1)
    d = getd(tot,e)                       # gets the multiplicative inverse
    while d<0:                            # i can probably replace this with mod
        d = d + tot
    return e,d,n

one set of keys generated:

e = 3daf16a37799d3b2c951c9baab30ad2d

d = 16873c0dd2825b2e8e6c2c68da3a5e25

n = dc2a732d64b83816a99448a2c2077ced

Answer 1

I assume you are doing this for fun and learning, and not for something that needs actual security.

Here is a few things I noticed (in no particular order):

1. You are not guaranteed that n will have length bits. It might be as short as bits - 4.

2. random is not a cryptographically secure random number generator.

3. It is common (and just as secure) to select the public exponent, e, to 65537. This is a prime, so you can replace the coprime-check with a divisor check.

4. It is a bit strange the search for e by setting e = tot (the coprime-check is bound to fail).

Otherwise it looks fine. The key seems to work fine, too. Do you have an example of a block that is not decrypting correctly? Remember that you can only encrypt data that is smaller than n. So with a 128-bit key (as in you example) you cannot encrypt all 128-bit numbers.

Answer 2

Mathematically, your n, e and d appear to respect the RSA rules (i.e. for every prime r which divides n, r² does not divide n, and d is an inverse of e modulo r-1). However, RSA is a bit more than that; it also mandates some padding rules, which govern how a message (a sequence of bytes) is to be transformed into an integer modulo n, and back. The standard padding (see PKCS#1) implies that at least 11 bytes are added to the message, and the result must still be no longer by n. Hence, with a 128-bit modulus like the one you show, the maximum input message length for encryption will be 5 bytes.

Also, some RSA implementations will refuse to work with RSA keys which are much too small for security. A 128-bit modulus can be factor in a matter of seconds (see this page for a factorization Java applet, which uses ECM and quadratic sieve to factor relatively small numbers such as yours). The current record in factorization is 768 bits; a modulus length of at least 1024 bits is recommended for short-term security. A typical RSA implementation will accept to use 512-bit keys, but many will reject anything shorter than that.

Another possible issue is in the relative order of p and q. The equations laid out in PKCS#1 assume that p > q (otherwise, there is an extra subtraction to perform in the CRT part). If you have p < q, then some implementations may get it wrong (I encountered that with Microsoft's RSA standard implementation in Windows). Just compare p with q and swap them if necessary.

Still on the practicality level, some widespread RSA implementations will refuse a RSA key such that the public exponent e does not fit within a 32-bit integer (this includes the RSA implementation used in Windows, in particular by Internet Explorer to connect to HTTPS Web sites -- so when I write "widespread" I mean it). RSA security does not seem to be impacted by the choice of e, so it is customary to choose a small e, which speeds up the part which uses the public key (i.e. encryption, as opposed to decryption, or signature verification, as opposed to signature generation). e = 3 is about the best you could do, but for traditional reasons (including an historical misunderstanding on an alleged weakness), e=65537 is often used. You just need to have e relatively prime to p-1 and q-1. In a practical implementation, you choose e first, then loop within the generation for p and q as long as they do not match that additional rule.

From a security point of view:

• Your generation process is not uniform, in that some prime integers will be selected more often than others. In particular, a prime p such that p+2 is also prime will almost never be selected. With a proper modulus size, this should not be an issue (that special kind of bias was studied and found out not to be a big issue) but it is bad public relations nonetheless.

• Your n may be a bit smaller than your target size, in case both p and q are close to the lower bound of their generation range. A simple way to avoid that is to restrict the range to [sqrt(2)*2^b-1, 2^b] for both p and q.

• I cannot vouch for the security of the random module you use. A cryptographically secure random number generator is not an easy thing to do.

• Generally speaking, properly implementing RSA without leaking confidential information through various side channels (timing, cache memory usage...) is not an easy task. If you want security in a practical setup, you should really really use an existing package. I believe that Python has ways to interface with OpenSSL.