The project has two Python projets: rsa-tasks and dh-tasks. In the first, you finish up code for RS encryption; you implement the Pollard-Rho factoring algorithm and compare it to trial division. And you attempt to crack a message attacking the modulus, to discover the factors, and then the decryption exponent.
The second file, you implement the ElGamal crypto-system. You begin your attack on the second challenge problem by implementing the big-step, litte-step method for discrete logs. You then attempt to crack a message enciphered with ElGamal.
Likewise, we use an "abstract" branch of mathematics, number theory, in the pursuit of the "craft" of cryptology.
My use of the word craft, rather than art or technology, is deliberate. Escher is said to have been inspired by the decorations of the Alhambra, in Granada, Spain. Cryptology goes back to the thoughts of Trithemius and other Alchemists, whose works were in a gray area between reason and emotion.
There are more connections. But in the manner of the alchemists, enough-said.
Complete the implementation of the RSA crypto system, in the class RSA in the project template file.
Write the Pollard Rho algorithm, which gives an advantage of a square-root over trial divisors. This algorithm can be used in challenge to crack the RSA key.
*** POLLARD RHO ALGORITHM ***
Given an n to factor
Choose a random starting points x and x_p, initially equal
Using the update function f(x)=x2+1, mod n:
Update x gets f(x) and x_p gets f(f(x))
Check the gcd between the difference x-x_p and n.
A non-trivial GCD is a factor of n. Return the factor
After about square root of n attempts, terminate having failed to find a factor of n
☆☆☆ RSA CHALLENGE ☆☆☆
☞ Find the plaintext ☜
RSA Params and ciphertext:
n = 13281020721221343268485383549533965497
e = 7
ciphtertext = 5902234696191027616157510009783082557
Complete the implementation of the ElGamal crypto system, in the class ElGamal in the project template file.
Take discrete log's using the big-step/small-step method for a square-root in power over brute force. You will need that boost in order to meet the challenge.
*** BIG STEP BABY STEP ALGORITHM ***
Make a table of about m = square root(n) slots.
Take h = gm and put hi into slot i of the table.
Sort the table.
Take the target z and calculate z g-j and look for a match
in the table
If a match is found then hi = z g-j which means
z = gm*i+j
☆☆☆ EL GAMAL CHALLENGE ☆☆☆
☞ Riddle: Dr who? ☜
Cryptotext hint:
public key (h) = 123
generator (g)= 5
prime (p) = 1333779268829507
three messages (g^r (p), m * h^r (p))
(879059454310780, 893889137529005)
(123475997005350, 1268193986275797)
(209827495157778, 790139893489473)
author: burton rosenberg
created: 13 nov 2019
update: 17 nov 2019