使用BigInteger实现的RSA算法没有得到正确的输出

Question

我是编程和网络安全方面的新手。我正试图为我的课堂作业实现RSA算法，但我没有得到正确的输出，所以请帮助我，它在解密时没有给出相同的纯文本。

下面是我的代码

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

输入:21

加密的MSG和解密的MSG每次都是随机的

Answer 1

您的phi计算错误。它一定是 = (p - 1)x(q - 1)，但它实际上是 = (p - 1)。你忘了再乘以一项。或者换句话说:

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

参见维基百科关于RSA的文章

---

其他注意事项:

未填充(教科书)RSA是不安全的。您需要实现安全填充，如OAEP。

RSA本身只能加密小于模数的数字。如果明文较大(不要忘记填充)，则需要混合加密。

Answer 2

我觉得目前公认的答案有点误导人，所以我想我会简单地编辑你的代码，将@Artom b的注释合并在一起。请将下面的代码与你的代码和@Krzysztof Cichocki发布的代码进行比较，看看你的错误在哪里。我也用BigInteger.ONE代替new BigInteger("1")，但这主要是一个外观上的改变。

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

下面是这个程序一次运行的输出:

 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

如果你仔细看加密消息1801088541，也许你可以推断出Artom在他说"无衬垫(教科书)RSA是不安全的"时所暗示的缺陷。您需要实现安全填充，例如OAEP。"

Answer 3

这对我来说是有效的，这是我写的非常旧的代码，但它有效，你需要实现pojo类，但那些只保留数字，是微不足道的实现。将每个步骤的结果与此进行比较，它应该有助于您调试代码。

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

类关键:

import java.math.BigInteger;
public class Key {
    BigInteger mod,pow;
}

类质数:

import java.io.Serializable;
import java.math.BigInteger;
public class Primes implements Serializable {
    BigInteger p,q,e;
}