RSA Encryption implementation in Python
This is a explanation of RSA encryption, along with a simple Python implementation of it.
RSA (Rivest–Shamir–Adleman) is one of the first public-key cryptosystems. The encryption key is public and it is different from the decryption key which is kept secret (private). In RSA, this asymmetry is based on the practical difficulty of the factorization of the product of two large prime numbers, the “factoring problem”. The acronym RSA is made of the initial letters of the surnames of Ron Rivest, Adi Shamir, and Leonard Adleman, who first publicly described the algorithm in 1978
It relies on the following principles:
- It is easy to find two distinct large primes pp and q.q.
- It is easy to multiply two large primes together, calculating n=pq.n=pq.
- However, given n=pq,n=pq, it is difficult to factor out pp and q.q. Given a, n and e , with 0 ( \mathrm < mod >n )$ is easy.
- But inversely, given $a ^ < e >( \mathrm < mod >n )$ ,e and n, it is difficult to calculate a.
- However, if the multiplicative inverse of e modulo $\phi ( n ) = ( q — 1 ) ( p — 1 )$ labelled d is given, then the previous calculation is easy.
- Calculating d from only n and e is difficult, but easy if the factorization of n=pq is known.
The steps for the algorithm is as follows:
Key Generation:
Encryption
To encrypt plaintext, first encode the plaintext (by padding it for example) so that it consists of blocks of size less than n. Then for block a, define $E(a)=a^e \pmod$ as the encryption function.
Decryption:
To decrypt ciphertext given by c = E(a) define $D(c) = c^d \pmod$. We then have $D(c)=D(E(a))=a^ \pmod$. For this to work, we need $a^=a \pmod$
Key Generation and Primality Tests
To start, our key generation requires us to generate two large primes p and q. To generate a large prime p,p, we start by deciding the number of bits we require in the prime. Let’s call this number b and let’s assume for simplicity that b>8 for all our intended purposes. In practice, b is usually between 512 and 2048. Then we proceed to check t+it+i for primality starting from i=0i=0 and onwards.
We use the Rabin-Miller algorithms to check if the number is prime or not. Then implement the RSA algorithm using the steps mentioned above
def generate_random_prime(bits, primality_test): """Generate random prime number with n bits.""" get_random_t = lambda: random.getrandbits(bits) | 1 bits | 1 p = get_random_t() for i in itertools.count(1): if primality_test(p): return p else: if i % (bits * 2) == 0: p = get_random_t() else: p += 2 # Add 2 since we are only interested in odd numbers @logged("%b %d %Y - %H:%M:%S") def simple_is_prime(n): """Returns True if n is a prime. False otherwise.""" if n % 2 == 0: return n == 2 if n % 3 == 0: return n == 3 k = 6L while (k - 1) ** 2 n: if n % (k - 1) == 0 or n % (k + 1) == 0: return False k += 6 return True def rabin_miller_is_prime(n, k=20): """ Test n for primality using Rabin-Miller algorithm, with k random witness attempts. False return means n is certainly a composite. True return value indicates n is *probably* a prime. False positive probability is reduced exponentially the larger k gets. """ b = basic_is_prime(n, K=100) if b is not None: return b m = n - 1 s = 0 while m % 2 == 0: s += 1 m //= 2 liars = set() get_new_x = lambda: random.randint(2, n - 1) while len(liars) k: x = get_new_x() while x in liars: x = get_new_x() xi = pow(x, m, n) witness = True if xi == 1 or xi == n - 1: witness = False else: for __ in xrange(s - 1): xi = (xi ** 2) % n if xi == 1: return False elif xi == n - 1: witness = False break xi = (xi ** 2) % n if xi != 1: return False if witness: return False else: liars.add(x) return True def basic_is_prime(n, K=-1): """Returns True if n is a prime, and False it is a composite by trying to divide it by two and first K odd primes. Returns None if test is inconclusive.""" if n % 2 == 0: return n == 2 for p in primes_list.less_than_hundred_thousand[:K]: if n % p == 0: return n == p return None def power(x, m, n): """Calculate x^m modulo n using O(log(m)) operations.""" a = 1 while m > 0: if m % 2 == 1: a = (a * x) % n x = (x * x) % n m //= 2 return a def extended_gcd(a, b): """Returns pair (x, y) such that xa + yb = gcd(a, b)""" x, lastx, y, lasty = 0, 1, 1, 0 while b != 0: q, r = divmod(a, b) a, b = b, r x, lastx = lastx - q * x, x y, lasty = lasty - q * y, y return lastx, lasty def multiplicative_inverse(e, n): """Find the multiplicative inverse of e mod n.""" x, y = extended_gcd(e, n) if x 0: return n + x return x def rsa_generate_key(bits): p = generate_random_prime(bits / 2) q = generate_random_prime(bits / 2) # Ensure q != p, though for large values of bits this is # statistically very unlikely while q == p: q = generate_random_prime(bits / 2) n = p * q phi = (p - 1) * (q - 1) # Here we pick a random e, but a fixed value for e can also be used. while True: e = random.randint(3, phi - 1) if fractions.gcd(e, phi) == 1: break d = multiplicative_inverse(e, phi) return (n, e, d) def rsa_encrypt(message, n, e): return modular.power(message, e, n) def rsa_decrypt(cipher, n, d): return modular.power(cipher, d, n) Updated: January 28, 2018
Rsa шифрование python код
RSA is the most widespread and used public key algorithm. Its security is based on the difficulty of factoring large integers. The algorithm has withstood attacks for more than 30 years, and it is therefore considered reasonably secure for new designs.
The algorithm can be used for both confidentiality (encryption) and authentication (digital signature). It is worth noting that signing and decryption are significantly slower than verification and encryption.
The cryptographic strength is primarily linked to the length of the RSA modulus n. In 2017, a sufficient length is deemed to be 2048 bits. For more information, see the most recent ECRYPT report.
Both RSA ciphertexts and RSA signatures are as large as the RSA modulus n (256 bytes if n is 2048 bit long).
The module Crypto.PublicKey.RSA provides facilities for generating new RSA keys, reconstructing them from known components, exporting them, and importing them.
As an example, this is how you generate a new RSA key pair, save it in a file called mykey.pem , and then read it back:
>>> from Crypto.PublicKey import RSA >>> >>> key = RSA.generate(2048) >>> f = open('mykey.pem','wb') >>> f.write(key.export_key('PEM')) >>> f.close() . >>> f = open('mykey.pem','r') >>> key = RSA.import_key(f.read())
Class defining an actual RSA key. Do not instantiate directly. Use generate() , construct() or import_key() instead.
- n (integer) – RSA modulus
- e (integer) – RSA public exponent
- d (integer) – RSA private exponent
- p (integer) – First factor of the RSA modulus
- q (integer) – Second factor of the RSA modulus
- invp (integer) – Chinese remainder component ( \(p^ \text q\) )
- invq (integer) – Chinese remainder component ( \(q^ \text p\) )
- u (integer) – Same as invp
exportKey ( format = ‘PEM’ , passphrase = None , pkcs = 1 , protection = None , randfunc = None ) ¶
- format (string) – The format to use for wrapping the key:
- ’PEM’. (Default) Text encoding, done according to RFC1421/RFC1423.
- ’DER’. Binary encoding.
- ’OpenSSH’. Textual encoding, done according to OpenSSH specification. Only suitable for public keys (not private keys).
Note This parameter is ignored for a public key. For DER and PEM, an ASN.1 DER SubjectPublicKeyInfo structure is always used.
- A 16 byte Triple DES key is derived from the passphrase using Crypto.Protocol.KDF.PBKDF2() with 8 bytes salt, and 1 000 iterations of Crypto.Hash.HMAC .
- The private key is encrypted using CBC.
- The encrypted key is encoded according to PKCS#8.
Specifying a value for protection is only meaningful for PKCS#8 (that is, pkcs=8 ) and only if a pass phrase is present too.
The supported schemes for PKCS#8 are listed in the Crypto.IO.PKCS8 module (see wrap_algo parameter).
ValueError – when the format is unknown or when you try to encrypt a private key with DER format and PKCS#1.
If you don’t provide a pass phrase, the private key will be exported in the clear!
- format (string) – The format to use for wrapping the key:
- ’PEM’. (Default) Text encoding, done according to RFC1421/RFC1423.
- ’DER’. Binary encoding.
- ’OpenSSH’. Textual encoding, done according to OpenSSH specification. Only suitable for public keys (not private keys).
Note This parameter is ignored for a public key. For DER and PEM, an ASN.1 DER SubjectPublicKeyInfo structure is always used.
- A 16 byte Triple DES key is derived from the passphrase using Crypto.Protocol.KDF.PBKDF2() with 8 bytes salt, and 1 000 iterations of Crypto.Hash.HMAC .
- The private key is encrypted using CBC.
- The encrypted key is encoded according to PKCS#8.
Specifying a value for protection is only meaningful for PKCS#8 (that is, pkcs=8 ) and only if a pass phrase is present too.
The supported schemes for PKCS#8 are listed in the Crypto.IO.PKCS8 module (see wrap_algo parameter).
ValueError – when the format is unknown or when you try to encrypt a private key with DER format and PKCS#1.
If you don’t provide a pass phrase, the private key will be exported in the clear!
Whether this is an RSA private key
A matching RSA public key.
A matching RSA public key.
Size of the RSA modulus in bits
The minimal amount of bytes that can hold the RSA modulus
Crypto.PublicKey.RSA. construct ( rsa_components , consistency_check = True ) ¶
Construct an RSA key from a tuple of valid RSA components.
The modulus n must be the product of two primes. The public exponent e must be odd and larger than 1.
In case of a private key, the following equations must apply:
- rsa_components (tuple) – A tuple of integers, with at least 2 and no more than 6 items. The items come in the following order:
- RSA modulus n.
- Public exponent e.
- Private exponent d. Only required if the key is private.
- First factor of n (p). Optional, but the other factor q must also be present.
- Second factor of n (q). Optional.
- CRT coefficient q, that is \(p^ \textq\) . Optional.
ValueError – when the key being imported fails the most basic RSA validity checks.
Returns: An RSA key object ( RsaKey ).
Crypto.PublicKey.RSA. generate ( bits , randfunc = None , e = 65537 ) ¶
Create a new RSA key pair.
The algorithm closely follows NIST FIPS 186-4 in its sections B.3.1 and B.3.3. The modulus is the product of two non-strong probable primes. Each prime passes a suitable number of Miller-Rabin tests with random bases and a single Lucas test.
- bits (integer) – Key length, or size (in bits) of the RSA modulus. It must be at least 1024, but 2048 is recommended. The FIPS standard only defines 1024, 2048 and 3072.
- randfunc (callable) – Function that returns random bytes. The default is Crypto.Random.get_random_bytes() .
- e (integer) – Public RSA exponent. It must be an odd positive integer. It is typically a small number with very few ones in its binary representation. The FIPS standard requires the public exponent to be at least 65537 (the default).
Returns: an RSA key object ( RsaKey , with private key).
Crypto.PublicKey.RSA. import_key ( extern_key , passphrase = None ) ¶
Import an RSA key (public or private).
- extern_key (stringorbyte string) – The RSA key to import. The following formats are supported for an RSA public key:
- X.509 certificate (binary or PEM format)
- X.509 subjectPublicKeyInfo DER SEQUENCE (binary or PEM encoding)
- PKCS#1 RSAPublicKey DER SEQUENCE (binary or PEM encoding)
- An OpenSSH line (e.g. the content of ~/.ssh/id_ecdsa , ASCII)
The following formats are supported for an RSA private key:
- PKCS#1 RSAPrivateKey DER SEQUENCE (binary or PEM encoding)
- PKCS#8 PrivateKeyInfo or EncryptedPrivateKeyInfo DER SEQUENCE (binary or PEM encoding)
- OpenSSH (text format, introduced in OpenSSH 6.5)
For details about the PEM encoding, see RFC1421/RFC1423.
Returns: An RSA key object ( RsaKey ).
ValueError/IndexError/TypeError – When the given key cannot be parsed (possibly because the pass phrase is wrong).
Crypto.PublicKey.RSA. oid = ‘1.2.840.113549.1.1.1’ ¶
Object ID for the RSA encryption algorithm. This OID often indicates a generic RSA key, even when such key will be actually used for digital signatures.