All of these RSA public keys were made with the same four prime numbers. Find al
ID: 655730 • Letter: A
Question
All of these RSA public keys were made with the same four prime numbers. Find all of the prime numbers used. Crack the RSA keys and decrypt the message for one of the keys. (HINT: gcd)
1 ## Each entry contains (e,n,encrypted message) 2 ## n = p*q for two primes p and q. e is the encrypting exponent. 3 ## Crack the rsa keys (without factoring) and decrypt the messages 4 ## The messages were all coded with A -- 00, B -- 01, and concatenated to get an integer.
keys_messages ={
1:(37, 174719560754626810678399686928347160023408881541073638558612810130006533530881985439439131089062055917, 7 2975159583345881885116026573184184189837958137328382350218028079241505911550441603680688684851119114), 8
2:(97, 370143788578343561265787544082451029738341881726182020740673317635584354562225922520764461458606223143, 9 296852344421229599030790256148910823665186161107024758697056156811281730254582268579809958686977945279),10
3:(17, 171979732109510265425754275749125858135964093823828466655172407249780244397114743583806197566583769663,11 32147349733627521528498223556837892020174518982420536534276658927915381555200000000000000000),12
4:(19, 303681432375117721292456922305735399853248815509805232886264503268182674740190249723544763576095518921,13 177751399575013577075992067966007149530633794460792277110491554629837655456079543847597734872458365679),14
5:(29, 212957900160907292418525676872990071851640717536062533500161570153905622087363370226481342361389699011,15 58954462888859012536779373196346588486075830283874192912233400076623185624398874485067730063709750115),16
0:(37, 376040591313872580373871821753626797245254164053235265147420898849033835447406550282141928044584979237,17 73116033121721407229545802276757088707010015832240258536840571582461272723239667901324555501179308380)18 }
Explanation / Answer
RSA is an important encryption technique first publicly invented by Ron Rivest, Adi Shamir, and Leonard Adleman in 1978. RSA is based on the fact that there is only one way to break a given integer down into a product of prime numbers, and a so-called trapdoor problem associated with this fact. It's easy to fall through a trap door, but pretty hard to climb up through it again; remember what the Sybil said:
John Dryden translation
The particular problem at work is that multiplication is pretty easy to do, but reversing the multiplication
[...] Sate sanguine divom,Tros Anchisiade, facilis descensus Averno;
noctes atque dies patet atri ianua Ditis;
sed revocare gradum superasque evadere ad auras,
hoc opus, hic labor est. O goddess-born of great Anchises' line,
The gates of hell are open night and day;
Smooth the descent, and easy is the way:
But to return, and view the cheerful skies,
In this the task and mighty labor lies.
John Dryden translation