I've managed to make 3 years of my uni course without resorting to the forums for help, but now i'm stuck. its still not due in for another 2 weeks, but i'd really like to get it out of the way.
assignment:
A 5 character `word' consisting of random capital letters has been encrypted using the RSA
algorithm. The word was encrypted in two 24 bit blocks using the ASCII values of the
characters (6510 to 9010) and padding the last block with a space (ASCII 3210). Each block
was formed by concatenating the 8 bit binary patterns of each of the characters in the block.
Thus creating two 24-bit intergers (actually 23-bit integers, as the MSB is zero). You are
provided with the public key used for the encryption and with the decimal values of the
encrypted blocks { see your summary sheet.
You are required to use a forward search using a Python dictionary/hash table to recover the
`word' that was encrypted.
i've been given the encrpytion exponent e = 7, n = 20340377 and encrypted blocks(decimal) = 14106558 4726600
so here's my script to deal with it (python):
# RSA demo
#encrypted blocks 14106558 4726600
encrypteda = "14106558"
encryptedb = "4726600"
import primes
import sys
n = 20340377 # n given
p = 4027 # two primes which make n
q = 5051
phi = (p-1)*(q-1) # the totient
# Try a sensible value for the encryption exponent
e = 7 # e given
# Check to see that this is OK
if primes.gcd(phi,e) != 1:
print 'e = %i was not a good choice' % e
exit(0)
# Find the value of the decryption exponent
d=primes.invmod(phi,e)
#d = 26140243
# Check that this is OK - should not have to do this
if d*e%phi != 1:
print '(d*e) mod (phi) != 1 - something really wrong here!!!'
sys.exit(0)
# Print out the prime numbers, n, the totient and the encryption and decryption exponents
print 'p = %i, q = %i, n = %i, phi = %i, e = %i, d = %i\n' % (p,q,n,phi,e,d)
#find first integer
for v in range(ord("A"),ord("Z")+1):
for w in range(ord("A"),ord("Z")+1):
for x in range(ord("A"),ord("Z")+1):
text = int(str(v)+str(w)+str(x))
etext = pow(text,e,n)
print "%i %i" %(text,etext)
if etext == encrypteda:
print "first word found."
#find second integer
for y in range(ord("A"),ord("Z")+1):
for z in range(ord("A"),ord("Z")+1):
text = int(str(y)+str(z)+"32")
etext = pow(text,e,n)
print "%i %i" %(text,etext)
if etext == encryptedb:
print "second word found."
sys.exit(0)
it should be self explanatory, but what i'm doing is cycling through all possible combinations of AAA to ZZZ, encrypting and comparing to see if it matches the first block, and then going through again for AA_ to ZZ_ ( _ = space ). but in neither case are there any matches..
anyone familiar with RSA willing to take a look and see where i've gone wrong?
