RSA

RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现今的三十多年里，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。RSA公开密钥密码体制。所谓的公开密钥密码体制就是使用不同的加密密钥与解密密钥，是一种“由已知加密密钥推导出解密密钥在计算上是不可行的”密码体制。

RSA的算法涉及三个参数，n、e1、e2。其中，n是两个大质数p、q的积，n的二进制表示时所占用的位数，就是所谓的密钥长度。e1和e2是一对相关的值，e1可以任意取。

算法过程

一、产生密钥

为了产生两个密钥，选取两个大素数，p和q,为了获得最大程度的安全性，两数的长度一样。计算乘积

n=p*q;
随机取加密密钥e,使得e 和（p-1)（q-1) 互素，最后采用扩展欧几里得算法计算解密密钥d，
```
d=e^-1 mod (p-1)(q-1)
```
注意

d和n也是互素。e和n是公开密钥，d是私人密钥。

RSA加解密的算法完全相同，设A为明文，B为密文，则：

A=B^d mod n；

B=A^e mod n；

公钥加密体制中，一般用公钥加密，私钥解密

e1和e2可以互换使用，即：

A=B^e mod n；

B=A^d mod n;

我们可以设计出一对公私密钥，加密密钥（公钥）为：KU =(e,n)=(3,33)，解密密钥（私钥）为：KR =(d,n)=(7,33)。

二、英文数字化

　将明文信息数字化，并将每块两个数字分组。假定明文英文字母编码表为按字母顺序排列数值，即：

三、明文加密

**加密消息m时，首先将它分为比n小的数据分组（采用二级制数，选取小于n的2的最大次幂），也就是说，若果p和n为100位的素数，那么n将有200位，每个消息分组m应该小于200位长 **

　用户加密密钥(3,33) 将数字化明文分组信息加密成密文。由C≡M^e(mod n)得：

四、密文解密

用户B收到密文，若将其解密，只需要计算 M≡c^d(mod n)

　用户B得到明文信息为：11，05，25。根据上面的编码表将其转换为英文，我们又得到了恢复后的原文“key”

e值

最常用的三个e值：3, 17, 65537(2^16+1).

X.509中建议采用65537^[1], PEM中建议采用3^{[37],PKCS#1建议采用3或65537}[1345].

PKCS#1填充

RSA在应用中一般采用PKCS#1的标准进行填充

注意

开头为00只为了保证原文大小小于私钥
对于私钥操作,你可以把BT的值设为01,这时PS填充的FF,那么用00字节就可以区分填充数据和明文数据对于公钥操作,填充的都是非00字节,也能够用00字节区分开。如果你使用私钥加密,建议你BT使用01,保证了安全性。
对于BT为02和01的,PS至少要有8个字节长,BT为02肯定是公钥加密,01肯定是私钥加密，要保证PS至少有八个字节长。因为EB= 00+BT+PS+00+D=k, 所以D<=k-11，所以当我们使用128字节密钥对数据进行加密时，明文数据的长度不能超过过128-11=117字节当RSA要加密数据大于 k-11字节时怎么办呢？把明文数据按照D的最大长度分块然后逐块加密,最后把密文拼起来就行。明文长度小于117ps处填充数据即可

附JAVA代码

/**

 * RSA algorithm.

 */

public static final String KEY_ALGORITHM = "RSA";

/**

 * digital signature algorithm

 */

public static final String SIGNATURE_ALGORITHM = "SHA256withRSA";

/**

 * Gets public key.

 */

private static final String PUBLIC_KEY = "RSAPublicKey";

/**

 * Gets private key.

 */

private static final String PRIVATE_KEY = "RSAPrivateKey";

/**

 * RSA maximum encryption text size.

 */

private static final int MAX_ENCRYPT_BLOCK = 117;

/**

 * RSA maximum decryption text size.

 */

private static final int MAX_DECRYPT_BLOCK = 128;

    /**

     * <p>

     * Use the private key to generate digital signatures for the information.

     * </p>

     *

     * @param data

     *            Encrypted data

     * @param PrivateKey

     *            Private Key (BASE64 encoding)

     * @return Digit signature (BASE64 encoding)

     * @throws Exception

     */

    public byte[] sign(byte[] data, String privateKey) {

        try {

            byte[] keyBytes = Base64Utils.decode(privateKey);

            PKCS8EncodedKeySpec pkcs8KeySpec = new PKCS8EncodedKeySpec(keyBytes);

            KeyFactory keyFactory;

            keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);

            PrivateKey privateK = keyFactory.generatePrivate(pkcs8KeySpec);

            Signature signature = Signature.getInstance(SIGNATURE_ALGORITHM);

            signature.initSign(privateK);

            signature.update(data);

            return signature.sign();

        } catch (NoSuchAlgorithmException | InvalidKeyException | SignatureException | InvalidKeySpecException e) {

            e.printStackTrace();

        }

        return null;

    }

    /**

     * <p>

     * Verify digit signature.

     * </p>

     *

     * @param data

     *            Encrypted data

     * @param publicKey

     *            Public Key(BASE64 encoding)

     * @param sign

     *            Digit signature

     *

     * @return result from verify

     * @throws Exception

     *

     */

    public boolean verify(byte[] data, String publicKey, byte[] sign) {

        byte[] keyBytes = Base64Utils.decode(publicKey);

        X509EncodedKeySpec keySpec = new X509EncodedKeySpec(keyBytes);

        KeyFactory keyFactory;

        try {

            keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);

            PublicKey publicK = keyFactory.generatePublic(keySpec);

            Signature signature = Signature.getInstance(SIGNATURE_ALGORITHM);

            signature.initVerify(publicK);

            signature.update(data);

            return signature.verify(sign);

        } catch (NoSuchAlgorithmException | InvalidKeySpecException | InvalidKeyException | SignatureException e) {

            // TODO Auto-generated catch block

            e.printStackTrace();

        }

        return false;

    }

    /**

     * <P>

     * Decrypted with the private key

     * </p>

     *

     * @param encryptedData

     *            Encrypted data

     * @param privateKey

     *            Private Key (BASE64 encoding)

     * @return decryptedData

     * @throws Exception

     */

    public byte[] decryptByPrivateKey(byte[] encryptedData, String privateKey) {

        byte[] keyBytes = Base64Utils.decode(privateKey);

        PKCS8EncodedKeySpec pkcs8KeySpec = new PKCS8EncodedKeySpec(keyBytes);

        KeyFactory keyFactory;

        try {

            keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);

            Key privateK = keyFactory.generatePrivate(pkcs8KeySpec);

            Cipher cipher = Cipher.getInstance(keyFactory.getAlgorithm());

            cipher.init(Cipher.DECRYPT_MODE, privateK);

            ByteArrayOutputStream out = new ByteArrayOutputStream();

            int inputLen = encryptedData.length;

            int offSet = 0;

            byte[] cache;

            int i = 0;

            // 对数据分段解密

            while (inputLen - offSet > 0) {

                if (inputLen - offSet > MAX_DECRYPT_BLOCK) {

                    cache = cipher.doFinal(encryptedData, offSet, MAX_DECRYPT_BLOCK);

                } else {

                    cache = cipher.doFinal(encryptedData, offSet, inputLen - offSet);

                }

                out.write(cache, 0, cache.length);

                i++;

                offSet = i * MAX_DECRYPT_BLOCK;

            }

            byte[] decryptedData = out.toByteArray();

            out.close();

            return decryptedData;

        } catch (Exception e) {

            e.printStackTrace();

        }

        return null;

    }

        /**

     * <p>

     * Encrypt with the public key.

     * </p>

     *

     * @param data

     *            Plain text

     * @param publicKey

     *            Public key(BASE64 encoding)

     * @return encryptedData

     * @throws Exception

     */

    public byte[] encryptByPublicKey(byte[] data, String publicKey) {

        byte[] keyBytes = Base64Utils.decode(publicKey);

        X509EncodedKeySpec x509KeySpec = new X509EncodedKeySpec(keyBytes);

        KeyFactory keyFactory;

        try {

            keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);

            Key publicK = keyFactory.generatePublic(x509KeySpec);

            // 对数据加密

            Cipher cipher = Cipher.getInstance(keyFactory.getAlgorithm());

            cipher.init(Cipher.ENCRYPT_MODE, publicK);

            ByteArrayOutputStream out = new ByteArrayOutputStream();

            int inputLen = data.length;

            int offSet = 0;

            byte[] cache;

            int i = 0;

            // 对数据分段加密

            while (inputLen - offSet > 0) {

                if (inputLen - offSet > MAX_ENCRYPT_BLOCK) {

                    cache = cipher.doFinal(data, offSet, MAX_ENCRYPT_BLOCK);

                } else {

                    cache = cipher.doFinal(data, offSet, inputLen - offSet);

                }

                out.write(cache, 0, cache.length);

                i++;

                offSet = i * MAX_ENCRYPT_BLOCK;

            }

            byte[] encryptedData = out.toByteArray();

            out.close();

            return encryptedData;

        } catch (Exception e) {

            // TODO Auto-generated catch block

            e.printStackTrace();

        }

        return null;

    }

304 ↩︎

巴特西

RSA详解

RSA