1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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$ $\endgroup$ – CodesInChaos Oct 30 '14 at 20:09
  • $\begingroup$ @CodesInChaos: How would I do that with the large numbers? $\endgroup$ – Jok3r Oct 30 '14 at 20:17
  • $\begingroup$ 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) $\endgroup$ – CodesInChaos Oct 30 '14 at 20:19
  • $\begingroup$ @CodesInChaos: Once I've done the calculations, how do I use d and m to decrypt? $\endgroup$ – Jok3r Oct 30 '14 at 20:22
  • $\begingroup$ Well, do you understand how RSA encryption and decryption work? $\endgroup$ – pg1989 Oct 31 '14 at 1:14
0
$\begingroup$

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 class RSADecrypt {

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);
        message256.add(k);
}
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 enter image description here

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – CodesInChaos Oct 31 '14 at 21:02
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.