Introduction to Cryptography with Open-Source Software

282 Cryptography with Open-Source Software

means that

a

x

= a

y

(mod n)

or that

a

x−y

= 1 (mod n)

and so

x − y = 0 (mod lcm(p − 1, q − 1)).

Therefore x and y ca n’t be found unless p and q can be determined, which

requires factoring n.

For example:

sage: p=next_prime(2^20);p

1048583

sage: q=next_prime(3^13);q

1594331

By some trial and error, it can be found that a = 2 has the required order:

sage: lcm(p-1,q-1)

835892870030

sage: mod(2,n).multiplicative_order()

835892870030

Now for some experiments with hashing. One expected result is that two

similar inputs should have very dissimilar outputs:

sage: a=Mod(2,n)

sage: a^str2num("A dog")

47971055483

sage: a^str2num("A cog") ...