RSA 算法原理

<一>基础

RSA算法非常简单，概述如下：
找两素数p和q
取n=p*q
取t=(p-1)*(q-1)
取任何一个数e,要求满足e<t并且e与t互素（就是最大公因数为1）
取d*e%t==1

(其中，公钥的exponent即RSA算法中的e, e通常是3，17和65537
X.509建议使用65537，PEM建议使用3，PKCS#1建议使用3或65537，一般来说，都是选择3。)

这样最终得到三个数： n  d  e

 

设消息为数M (M <n)
设c=(M**d)%n就得到了加密后的消息c
设m=(c**e)%n则 m == M，从而完成对c的解密。
注：**表示次方,上面两式中的d和e可以互换。

在对称加密中：
n e两个数构成公钥，可以告诉别人；
n d两个数构成私钥，d自己保留，不让任何人知道。
给别人发送的信息使用d加密，只要别人能用e解开就证明信息是由你发送的
别人给你发送信息时使用e加密，这样只有拥有d的你能够对其解密。


rsa的安全性在于对于一个大数n，没有有效的方法能够将其分解
从而在已知n d的情况下无法获得e；同样在已知n e的情况下无法
求得d。

 

以上原理详见维基百科：http://zh.wikipedia.org/wiki/RSA%E5%8A%A0%E5%AF%86%E6%BC%94%E7%AE%97%E6%B3%95#.E5.85.AC.E9.92.A5.E5.92.8C.E7.A7.81.E9.92.A5.E7.9A.84.E4.BA.A7.E7.94.9F


<二>实践

package com.yajun.rsa;

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

/**
 * RSA 算法原理实现
 * 
 * @author Administrator
 */
public class RSA implements Serializable {
    private static final long         serialVersionUID = 7935341891569534021L;

    private final static BigInteger   one              = BigInteger.ONE;
    private final static SecureRandom random           = new SecureRandom();
    private BigInteger                privateKey       = null;
    private BigInteger                publicKey        = null;
    private BigInteger                modulus          = null;
    private BigInteger                p1               = null;
    private BigInteger                p2               = null;
    //Ces variables doivent être initialisé pour l'encrytage de données.
    private BigInteger                modulusE;
    private BigInteger                publicKeyE;
    private int                       N;
    private BigInteger                phi0;

    public RSA(int N) {
        this.N = N;
        // generate an N-bit (roughly) public and private key
        //clés privé
        //p1
        p1 = BigInteger.probablePrime(N / 2, random);
        //p2
        p2 = BigInteger.probablePrime(N / 2, random);
        //t
        phi0 = (p1.subtract(one)).multiply(p2.subtract(one));
        //n
        modulus = p1.multiply(p2);
        //d
        setPrivateKey();
        //e
        publicKey = privateKey.modInverse(phi0);
        modulusE = modulus;
        publicKeyE = publicKey;
    }

    public BigInteger getModulus() {
        return modulus;
    }

    public BigInteger getPublicKey() {
        return publicKey;
    }

    public void setPublicKey(BigInteger p, BigInteger n) {
        publicKeyE = p;
        modulusE = n;
    }

    /**
     * 这部分没怎么看懂
     */
    private void setPrivateKey() {
        do {
            privateKey = BigInteger.probablePrime(N / 2, random);
        } while (privateKey.gcd(phi0).intValue() != 1 || privateKey.compareTo(modulus) != -1
                || privateKey.compareTo(p1.max(p2)) == -1);
    }

    /**
     * 加密
     * 
     * @param message
     * @return
     */
    public BigInteger encrypt(BigInteger message) {
        BigInteger rep = null;
        String str_message = new String(message.toByteArray());
        if (message != null) {
            if (str_message.length() <= (N / 8)) {
                if (publicKeyE != null && modulusE != null
                        && message.toByteArray().length < Integer.MAX_VALUE) {
                    rep = message.modPow(publicKeyE, modulusE);
                }
            }
        }
        return rep;
    }

    /**
     * 加密，公式比较容易看懂
     * 
     * @param message
     * @param publicKeyP
     * @param modulusP
     * @return
     */
    public BigInteger encrypt(BigInteger message, BigInteger publicKeyP, BigInteger modulusP) {
        BigInteger rep = null;
        String str_message = new String(message.toByteArray());
        if (str_message.length() <= (N / 8)) {
            if (publicKeyP != null && modulusP != null
                    && message.toByteArray().length < Integer.MAX_VALUE) {
                rep = message.modPow(publicKeyP, modulusP);
            }
        }
        return rep;
    }

    /**
     * 解密，公式也比较容易看懂
     * 
     * @param encrypted
     * @return
     */
    public BigInteger decrypt(BigInteger encrypted) {
        return encrypted.modPow(privateKey, modulus);
    }

    public String toString() {
        String s = "";
        s += "public  = " + publicKey + "\n";
        s += "modulus = " + modulus;
        return s;
    }

    public static void main(String[] args) {
        BigInteger message = BigInteger.valueOf(88);
        RSA rsa = new RSA(512);
        BigInteger enInteger = rsa.encrypt(message);
        BigInteger deInteger = rsa.decrypt(enInteger);
        System.out.println(enInteger);
        System.out.println(deInteger);
    }
}