Skip to content
{{ message }}

Instantly share code, notes, and snippets.

# tylerl/rsa.py

Created Sep 24, 2011
RSA Explained in Python
 #!/usr/bin/env python # This example demonstrates RSA public-key cryptography in an # easy-to-follow manner. It works on integers alone, and uses much smaller numbers # for the sake of clarity. ##################################################################### # First we pick our primes. These will determine our keys. ##################################################################### # Pick P,Q,and E such that: # 1: P and Q are prime; picked at random. # 2: 1 < E < (P-1)*(Q-1) and E is co-prime with (P-1)*(Q-1) P=97 # First prime Q=83 # Second prime E=53 # usually a constant; 0x10001 is common, prime is best ##################################################################### # Next, some functions we'll need in a moment: ##################################################################### # Note on what these operators do: # % is the modulus (remainder) operator: 10 % 3 is 1 # // is integer (round-down) division: 10 // 3 is 3 # ** is exponent (2**3 is 2 to the 3rd power) # Brute-force (i.e. try every possibility) primality test. def isPrime(x): if x%2==0 and x>2: return False # False for all even numbers i=3 # we don't divide by 1 or 2 sqrt=x**.5 while i T: raise Exception("E must be > 1 and < T") if T%E==0: raise Exception("E is not coprime with T") ##################################################################### # Now that we've validated our random numbers, we derive our keys. ##################################################################### # Product of P and Q is our modulus; the part determines as the "key size". MOD=P*Q # Private exponent is inverse of public exponent with respect to (mod T) D = find_inverse(E,T) # The modulus is always needed, while either E or D is the exponent, depending on # which key we're using. D is much harder for an adversary to derive, so we call # that one the "private" key. print "public key: (MOD: %i, E: %i)" % (MOD,E) print "private key: (MOD: %i, D: %i)" % (MOD,D) # Note that P, Q, and T can now be discarded, but they're usually # kept around so that a more efficient encryption algorithm can be used. # http://en.wikipedia.org/wiki/RSA#Using_the_Chinese_remainder_algorithm ##################################################################### # We have our keys, let's do some encryption ##################################################################### # Here I only focus on whether you're applying the private key or # applying the public key, since either one will reverse the other. import sys print "Enter \">NUMBER\" to apply private key and \"': key = D else: print "Must start with either < or >" print "Enter \">NUMBER\" to apply private key and \"NUMBER\" to apply private key and \"= MOD: print "Only values up to %i can be encoded with this key (choose bigger primes next time)" % (MOD,) continue # Note that the pow() built-in does modulo exponentation. That's handy, since it saves us having to # implement that ablity. # http://en.wikipedia.org/wiki/Modular_exponentiation after = pow(before,key,MOD) #encrypt/decrypt using this ONE command. Surprisingly simple. if key == D: print "PRIVATE(%i) >> %i" %(before,after) else: print "PUBLIC(%i) >> %i" %(before,after)

### MichelPoulain commented Mar 1, 2017

 Perfect explanation! Thanks for your answer to «Is there a simple example of an Asymmetric encryption/decryption routine?» I was looking for this kind of routine to encrypt numbers inferiors to 1 billion with results inferiors to 1 billion. (I'm limited in string length). Is this routine safe for that task? Can we computed (by brute force?) the private key from and only the public key and the modulus?

### jdavid54 commented Feb 6, 2018

 The condition to have an inverse in line 63 is wrong ! E and T must be coprime then their gcd must be 1 and not T%E!=0 as given for the raise condition if T%E==0: raise Exception("E is not coprime with T") must be if gcd(E,T)!=1: raise Exception("E is not coprime with T")
to join this conversation on GitHub. Already have an account? Sign in to comment