#!/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. |
defisPrime(x): |
ifx%20andx>2: returnFalse# False for all even numbers |
i=3# we don't divide by 1 or 2 |
sqrt=x**.5 |
whilei<sqrt: |
ifx%i0: returnFalse |
i+=2 |
returnTrue |
# Part of find_inverse below |
# See: http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm |
defeea(a,b): |
ifb0:return (1,0) |
(q,r) = (a//b,a%b) |
(s,t) =eea(b,r) |
return (t, s-(q*t) ) |
# Find the multiplicative inverse of x (mod y) |
# see: http://en.wikipedia.org/wiki/Modular_multiplicative_inverse |
deffind_inverse(x,y): |
inv=eea(x,y)[0] |
ifinv<1: inv+=y#we only want positive values |
returninv |
##################################################################### |
# Make sure the numbers we picked above are valid. |
##################################################################### |
ifnotisPrime(P): raiseException('P (%i) is not prime'% (P,)) |
ifnotisPrime(Q): raiseException('Q (%i) is not prime'% (Q,)) |
T=(P-1)*(Q-1) # Euler's totient (intermediate result) |
# Assuming E is prime, we just have to check against T |
ifE<1orE>T: raiseException('E must be > 1 and < T') |
ifT%E0: raiseException('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. |
importsys |
print'Enter '>NUMBER' to apply private key and '<NUMBER' to apply public key; 'Q' to quit.' |
whileTrue: |
sys.stdout.write('? ') |
line=sys.stdin.readline().strip() |
ifnotline: break |
ifline'q'orline'Q': break |
ifline[0]'<': key=E |
elifline[0]'>': key=D |
else: |
print'Must start with either < or >' |
print'Enter '>NUMBER' to apply private key and '<NUMBER' to apply public key; 'Q' to quit.' |
continue |
line=line[1:] |
try: before=int(line) |
exceptValueError: |
print'not a number: '%s''% (line) |
print'Enter '>NUMBER' to apply private key and '<NUMBER' to apply public key; 'Q' to quit.' |
continue |
ifbefore>=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. |
ifkeyD: print'PRIVATE(%i) >> %i'%(before,after) |
else: print'PUBLIC(%i) >> %i'%(before,after) |
Generate google translate api key. 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. https://brainnew203.weebly.com/diablo-3-cd-key-generator-no-survey.html. (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? |
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%E0: raise Exception('E is not coprime with T') must be if gcd(E,T)!=1: raise Exception('E is not coprime with T') |