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

Answer 1

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."

Answer 2

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.

Answer 3

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;
}