# RSA Decryption given n, e, and phi(n)

my cryptography professor gave us this problem for extra credit a while back and I attempted it but I didn't get it correct. I have gone back to it, but I'm even more lost now than I was the first time (HEADS UP: my professor gave us some long numbers to work with)

Let N=

 217480967426598493570186980401996167920452820950992854687035132
726376073118953668642571927853352339590583090604658684239518232
853572979131254064492477407811878270605929141044977950456991658
882119063692415321357447387047198644556238539408419478596527501
23329821235383771649185149402914522002819011319590369529

And e=65537 be a public key for the RSA cryptosystem


The ciphertext is:

503502864628940396744635609090061402472498491194463969923479322
089849770618612322621019979098961384995354204702163333139805707
759660081519394083069273037638282947420860920004667666344095765
710257079484209928467972889843783133155796096794854080979925590
2703014867201045003016001267189341232653910252303505881


And we determine that:

 phi(n)=
217480967426598493570186980401996167920452820950992854687035132
726376073118953668642571927853352339590583090604658684239518232
853572979131254064492477381836798664822705327075966772445783246
838640744314191496615629393761046078697812048683249333166663641
55001553295827687037711471146642763970634674131635418276


I was supposed to decode the message (The message was converted into a number by writing it in base 256 using the ASCII codes for the individual characters)

If anyone could provide a step by step explanation of how I go about doing this, I would greatly appreciate it.

• 1) Compute d as the Modular multiplicative inverse of e, i.e. $d=e^-1 \bmod \phi(n)$ using extended euclidean 2) compute $m=c^d \bmod n$ Oct 30 '14 at 20:09
• @CodesInChaos: How would I do that with the large numbers? Oct 30 '14 at 20:17
• Use a big integer library, most programming languages either contain one (at least C# and Python do) or have a readily available third party implementation. (unfortunately the wolfram alpha link above doesn't work, it truncated phi) Oct 30 '14 at 20:19
• @CodesInChaos: Once I've done the calculations, how do I use d and m to decrypt? Oct 30 '14 at 20:22
• Well, do you understand how RSA encryption and decryption work? Oct 31 '14 at 1:14

I'm sorry @J0ker, I found new answer (maybe there are errors value in my first answer).

My new answer $m =$

49314552466695255586203088029816774295110376055124609941914798033775741215800363731230533018093001338140450279336308798327354131807371119497156895131357788895448541113895626439002123851


I try to convert $m$ to base 256

[75, 110, 111, 119, 108, 101, 100, 103, 101, 32, 105, 115, 32, 112, 111, 119, 101, 114, 46, 32, 80, 108, 101, 97, 115, 101, 32, 117, 115, 101, 32, 116, 104, 101, 32, 112, 111, 119, 101, 114, 32, 121, 111, 117, 32, 104, 97, 118, 101, 32, 102, 111, 114, 32, 103, 111, 111, 100, 44, 32, 97, 110, 100, 32, 110, 111, 116, 32, 102, 111, 114, 32, 101, 118, 105, 108, 46]


with ASCII code

Knowledge is power. Please use the power you have for good, and not for evil.


try this (in Java Language)

import java.math.BigInteger; import java.util.ArrayList;

public static void main (String[] args) {

BigInteger N,phiN,e,d,m,c;

// chipertext c, plaintext m

N = new BigInteger ("21748096742659849357018698040199616792045282095099285468703513272637607311895366864257192785335233959058309060465868423951823285357297913125406449247740781187827060592914104497795045699165888211906369241532135744738704719864455623853940841947859652750123329821235383771649185149402914522002819011319590369529");

e = new BigInteger ("65537");

c = new BigInteger ("5035028646289403967446356090900614024724984911944639699234793220898497706186123226210199790989613849953542047021633331398057077596600815193940830692730376382829474208609200046676663440957657102570794842099284679728898437831331557960967948540809799255902703014867201045003016001267189341232653910252303505881");

phiN = new BigInteger ("21748096742659849357018698040199616792045282095099285468703513272637607311895366864257192785335233959058309060465868423951823285357297913125406449247738183679866482270532707596677244578324683864074431419149661562939376104607869781204868324933316666364155001553295827687037711471146642763970634674131635418276");

d = e.modInverse(phiN);
m = c.modPow(d, N);

System.out.println("d = "+d);
System.out.println("m = "+m);

System.out.println("m in base 256 = "+base256(m));
System.out.println("Convert with ASCII \n"+ Encode256(base256(m)));

}

static ArrayList<BigInteger> base256 (BigInteger M) {
BigInteger base = new BigInteger("256");
ArrayList<BigInteger> message256 = new ArrayList<BigInteger>();
BigInteger sisa=M;
BigInteger k;
double z = Double.parseDouble(M.toString());
double p = Math.floor(Math.log(z)/Math.log(256));
int r = (int) p;
for (int j=0;j<=r;j++){
k=sisa.mod(base);
sisa=sisa.divide(base);
}
return message256;
}

static String Encode256 (ArrayList<BigInteger> ascii) {
String ascii256="";
int g,dmp;
for (int i=0;i<ascii.size();i++) {
g = Integer.parseInt(""+ascii.get(i));
ascii256=ascii256+( (char) g );
}
return ascii256;
}


}

this is my result from this code

• 1) If there are errors in your first answer, edit it to correct it, instead of posting a new one. 2) I recommend including the essential parts of your code in the answer. An answer in stackexchange should be able to stand on its own, without external resources that might disappear over time. Oct 31 '14 at 21:02

We have $d = e^{-1} \pmod{ \phi(N) }$, this implies that $m = c ^ d \pmod{N}$