All of these RSA public keys were made with the same four prime numbers. Find al
ID: 658191 • 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
Answer: 2,3,5