Not getting proper output for RSA algorithm implemented with BigInteger

Question

I am new to programming and network security. I am trying to implement RSA algorithm for my classwork but I am not getting correct output so please help me, its not giving the same plain text while decrypting.

following is my code

import java.security.*;
import java.lang.*;
import java.math.*;

public class RSAalgo
{
    BigInteger p,q,n,d,e,ph,t;
    SecureRandom r;

    public RSAalgo()
    {
        r=new SecureRandom();
        p=new BigInteger(512,100,r);
        q=new BigInteger(512,100,r);

        System.out.println("\n RSA ALGO");
        System.out.println("\n Prime No P : "+p.intValue());
        System.out.println("\n Prime no Q : "+q.intValue());

        n=p.multiply(q);
        ph=(p.subtract(new BigInteger("1")));

        e = new BigInteger("2");

        while((ph.gcd(e).intValue()>1)||(e.compareTo(ph)!=-1))
        e=e.add(new BigInteger("1"));

        d=e.modInverse(ph);

        System.out.println("public key = "+n.intValue()+", "+e.intValue());
        System.out.println("Private key = "+n.intValue()+", "+d.intValue());

        BigInteger msg=new BigInteger("21");        
        System.out.println("Message is "+msg);

        BigInteger enmsg=encrypt(msg,e,n);      
        System.out.println("Encrypted message is "+enmsg.intValue());

        BigInteger demsg=decrypt(enmsg,d,n);
        System.out.println("Decrypted message is "+demsg.intValue());

    }

    BigInteger encrypt(BigInteger msg,BigInteger e, BigInteger n)
    {
        return msg.modPow(e,n);
    }

    BigInteger decrypt(BigInteger msg,BigInteger d, BigInteger n)
    {
        return msg.modPow(d,n);
    }


    public static void main(String args[])
    {
        new RSAalgo();
    }
}

input: 21

encrypted msg and decrypted msg are random everytime

Please add information: what input do you give; and what output comes out of it; and what would expect otherwise? And spent a few minutes to indent/format your code better to make it easier to read. — GhostCat
– GhostCat, Commented Aug 26, 2016 at 11:51
r=new SecureRandom(); p=new BigInteger(512,100,r); q=new BigInteger(512,100,r); generates prime numbers — Parvez
– Parvez, Commented Aug 26, 2016 at 12:03
You are wrong there. I am posting an answer below, there are more than a few errors — vish4071
– vish4071, Commented Aug 26, 2016 at 12:06

Artjom B. · Accepted Answer · 2016-08-26 17:51:20Z

1

Your phi is calculated incorrectly. It must be phi = (p - 1)x(q - 1), but it actually is phi = (p - 1). You forgot to multiply an additional term. Or in other words:

ph = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));

See the Wikipedia article on RSA.

Other considerations:

Unpadded (textbook) RSA is insecure. You need to implement secure padding such as OAEP.

RSA itself can only encrypt something that is numerically smaller than the modulus. If your plaintext is larger (don't forget the padding), then you need hybrid encryption.

answered Aug 26, 2016 at 17:51

Artjom B.

62k26 gold badges137 silver badges236 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

President James K. Polk · Accepted Answer · 2016-09-13 11:21:34Z

I feel the accepted answer is somewhat misleading at this point in time, so I thought I would simply edit your code to incorporate the comments of @Artom B. Please compare the code below to your code and the code posted by @Krzysztof Cichocki to see where your mistakes are. I also used BigInteger.ONE instead of new BigInteger("1") but that is mostly a cosmetic change.

import java.math.BigInteger;
import java.security.SecureRandom;

public class RSAalgo {
    BigInteger p, q, n, d, e, ph, t;
    SecureRandom r;

    public RSAalgo() {
        r = new SecureRandom();
        p = new BigInteger(512, 100, r);
        q = new BigInteger(512, 100, r);

        System.out.println("\n RSA ALGO");
        System.out.println("\n Prime No P : " + p);
        System.out.println("\n Prime no Q : " + q);

        n = p.multiply(q);
        ph = (p.subtract(BigInteger.ONE)).multiply(q.subtract(BigInteger.ONE));

        e = new BigInteger("2");

        while ((ph.gcd(e).intValue() > 1) || (e.compareTo(ph) != -1))
            e = e.add(BigInteger.ONE);

        d = e.modInverse(ph);

        System.out.println("public key = " + n + ", " + e);
        System.out.println("Private key = " + n + ", " + d);

        BigInteger msg = new BigInteger("21");
        System.out.println("Message is " + msg);

        BigInteger enmsg = encrypt(msg, e, n);
        System.out.println("Encrypted message is " + enmsg);

        BigInteger demsg = decrypt(enmsg, d, n);
        System.out.println("Decrypted message is " + demsg);

    }

    BigInteger encrypt(BigInteger msg, BigInteger e, BigInteger n) {
        return msg.modPow(e, n);
    }

    BigInteger decrypt(BigInteger msg, BigInteger d, BigInteger n) {
        return msg.modPow(d, n);
    }

    public static void main(String args[]) {
        new RSAalgo();
    }
}

Here is the output from one run of this program:

 RSA ALGO

 Prime No P : 7385887478481685426993214602368774899822361657609273024676297215761456907576361503385555975157308399849328828600179690472123592317381855278505714472809701

 Prime no Q : 9697854674813414062564435136414673948111723349180632387293117086433856431627811334553449685531026027836405752904433352501524789604919970659422354853067003
public key = 71627263410839472181079411740104072578551746566830443612142954116975018729181714598122158332496727078551292122128676328582232680698169145364025223095271546289887132569293490463703371501767853891145781471271218830484185948403241381862567321829707888222282401077404230822288043321027073755612191149650621396103, 7
Private key = 71627263410839472181079411740104072578551746566830443612142954116975018729181714598122158332496727078551292122128676328582232680698169145364025223095271546289887132569293490463703371501767853891145781471271218830484185948403241381862567321829707888222282401077404230822288043321027073755612191149650621396103, 10232466201548496025868487391443438939793106652404349087448993445282145532740244942588879761785246725507327446018382332654604668671167020766289317585038789886592139896313428700864804674045572279580110668766543837295697679012843168241389911832006742841122102191831818029892152810377878779112321888797327931343
Message is 21
Encrypted message is 1801088541
Decrypted message is 21

If you look carefully at the encrypted message 1801088541 perhaps you can deduce the flaw that Artom alluded to when he stated "Unpadded (textbook) RSA is insecure". You need to implement secure padding such as OAEP."

Krzysztof Cichocki · Accepted Answer · 2016-08-26 12:15:48Z

0

This works for me, it is very old code written by me but it works, you need to implement the pojo classes, but those only hold the numbers and are trivial to implement. Compare the results from each step with this, it should help you to debug your code.

public class RSAService {
    private Key PublicKey, PrivateKey;

        public Primes newPrimes(int n) {
            Random r= new Random();
            Primes p = new Primes();
            p.p= BigInteger.probablePrime(n, r);
            p.q= BigInteger.probablePrime(n, r);
            p.e= BigInteger.probablePrime(n, r);
            return p;
        }


    public BigInteger extEuklides(BigInteger nwd_a, BigInteger nwd_b) {

                   BigInteger a, b;
           BigInteger r, q;
           BigInteger x, x1, x2;
           BigInteger y, y1, y2;
           BigInteger nwd;

               // a must be greater than b
           if (nwd_b.compareTo(nwd_a)>0)
           {
              nwd = nwd_b;
              nwd_b = nwd_a;
              nwd_a = nwd;
           }

           //initialize a and b
           a = nwd_a;
           b = nwd_b;

           //initialize r and nwd
           q = a.divide(b);
           r = a.subtract(q.multiply(b));
           nwd = b;

           //initialize x and y
           x2 = BigInteger.ONE;
           x1 = BigInteger.ZERO;
           y2 = BigInteger.ZERO;
           y1 = BigInteger.ONE;
           x  = BigInteger.ONE;
           y  = y2.subtract(q.subtract(BigInteger.ONE).multiply(y1));

           while (r.compareTo(BigInteger.ZERO)!= 0)
           {

              a = b;
              b = r;

              x = x2.subtract(q.multiply(x1));
              x2 = x1;
              x1 = x;

              y = y2.subtract(q.multiply(y1));
              y2 = y1;
              y1 = y;

              nwd = r;
              q = a.divide(b);
              r = a.subtract(q.multiply(b));
           }

           if (nwd.compareTo(BigInteger.ONE) == 0)
            // System.out.println(nwd_b+" * "+y+" mod "+nwd_a+" = 1");
                   {return y;}
                   return null;
    }

        public void newKeys(int size) {
            BigInteger fn;
            BigInteger n,d;
            Primes prim;
            do {
                 prim=newPrimes(size);
                 n= prim.p.multiply(prim.q);
                 fn= prim.p.subtract(BigInteger.ONE).multiply(prim.q.subtract(BigInteger.ONE));
            } while ((d=extEuklides(fn, prim.e))==null);
            PublicKey.mod=n;
            PublicKey.pow=d;
            PrivateKey.mod=n;
            PrivateKey.pow=prim.e;
        }

        public static void main(String[] args) {
            newKeys(512);
            // use the public and private key to encode decode by modpow

        }
}

class Key:

import java.math.BigInteger;

public class Key {
    BigInteger mod,pow;
}

class Primes:

import java.io.Serializable;
import java.math.BigInteger;

public class Primes implements Serializable {
    BigInteger p,q,e;
}

edited Aug 26, 2016 at 12:15

answered Aug 26, 2016 at 12:06

Krzysztof Cichocki

6,4421 gold badge20 silver badges33 bronze badges

4 Comments

vish4071 Over a year ago

And how does this answer his question?

Krzysztof Cichocki Over a year ago

He can compare the results to do own debugging

vish4071 Over a year ago

How do you debug your own code following some other code, with totally different approach?

Krzysztof Cichocki Over a year ago

He has an error in algorithm, my algorithm is the same RSA - it has same steps, so it is not very different approach. And he can easily compare the results of each step to find out what is wrong in His approach.

Collectives™ on Stack Overflow

Not getting proper output for RSA algorithm implemented with BigInteger

3 Answers 3

Comments

Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related