Search code examples
pythonrsa

RSA Python Issue

I am having an issue with getting my python program to decrypt a message with an RSA problem. For some reason my Python program is stalling, really just not outputting anything. Anyone got an idea as to why?

n = 23952937352643527451379227516428377705004894508566304313177880191662177061878993798938496818120987817049538365206671401938265663712351239785237507341311858383628932183083145614696585411921662992078376103990806989257289472590902167457302888198293135333083734504191910953238278860923153746261500759411620299864395158783509535039259714359526738924736952759753503357614939203434092075676169179112452620687731670534906069845965633455748606649062394293289967059348143206600765820021392608270528856238306849191113241355842396325210132358046616312901337987464473799040762271876389031455051640937681745409057246190498795697239
p = 153143042272527868798412612417204434156935146874282990942386694020462861918068684561281763577034706600608387699148071015194725533394126069826857182428660427818277378724977554365910231524827258160904493774748749088477328204812171935987088715261127321911849092207070653272176072509933245978935455542420691737433
c = 18031488536864379496089550017272599246134435121343229164236671388038630752847645738968455413067773166115234039247540029174331743781203512108626594601293283737392240326020888417252388602914051828980913478927759934805755030493894728974208520271926698905550119698686762813722190657005740866343113838228101687566611695952746931293926696289378849403873881699852860519784750763227733530168282209363348322874740823803639617797763626570478847423136936562441423318948695084910283653593619962163665200322516949205854709192890808315604698217238383629613355109164122397545332736734824591444665706810731112586202816816647839648399
e = 65537
q = 156408916769576372285319235535320446340733908943564048157238512311891352879208957302116527435165097143521156600690562005797819820759620198602417583539668686152735534648541252847927334505648478214810780526425005943955838623325525300844493280040860604499838598837599791480284496210333200247148213274376422459183
phi = (q-1)*(p-1)
d = pow(e,-1,phi)
m = pow(c,d)%n
print(m)

I apologize for the weird code formatting. Thanks in advance.

Solution

  • Assuming the math is correct (I didn't check), you definitely want to change this:

    m = pow(c,d)%n

    to this:

    m = pow(c, d, n)

    The first spelling computes c**d to full precision before dividing by n to find the remainder. That can be enormously expensive. The second way keeps reducing intermediate results, under the covers, mod n all along, and never needs to do arithmetic in integers larger than about n**2.

    So, replacing the last line of your code and continuing:

    >>> m = pow(c, d, n) # less than an eyeblink
>>> m
14311663942709674867122208214901970650496788151239520971623411712977120586163535880168563325
>>> pow(m, e, n) == c
True

    So the original "message" (c) is recovered by doing modular exponentiation to powers d and e in turn.