使用 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

每次加密的消息和解密的消息都是随机的

Answer 1

这对我有用，这是我写的非常古老的代码，但它确实有效，你需要实现 pojo classes，但那些只包含数字并且实现起来很简单。将每一步的结果与此进行比较，它应该可以帮助您调试代码。

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 键：

import java.math.BigInteger;

public class Key {
    BigInteger mod,pow;
}

class素数：

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

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

Answer 2

您的 phi 计算有误。一定是phi = (p - 1)x(q - 1)，但实际上是phi = (p - 1)。你忘了乘以一个附加项。或者换句话说：

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

请参阅 RSA 上的维基百科文章。

其他注意事项：

Unpadded（教科书）RSA 不安全。您需要实施安全填充，例如 OAEP。

RSA本身只能加密数值小于模数的东西。如果你的明文更大（不要忘记填充），那么你需要 hybrid encryption.

Answer 3

我觉得此时接受的答案有点误导，所以我想我会简单地编辑你的代码以合并@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 在陈述 "Unpadded (textbook) RSA is insecure" 时提到的缺陷。您需要实施安全填充，例如 OAEP。"

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

Not getting proper output for RSA algorithm implemented with BigInteger

java

encryption

algorithm

rsa