Introduce

RSA公钥加密算法是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。1978年首次公布，当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。

RSA是目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的绝大多数密码攻击，已被ISO推荐为公钥数据加密标准。

RSA算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但是想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。

1983年麻省理工学院在美国为RSA算法申请了专利。这个专利2000年9月21日失效。由于该算法在申请专利前就已经被发表了，在世界上大多数其它地区这个专利权不被承认。

A Method For Obtaining Digital Signatures And Public Key Cryptosystems

RSA （Rivest, Shamir, Adelman）

Basic

在公开密钥密码体制中，加密密钥（即公开密钥）PK是公开信息，而解密密钥（即秘密密钥）SK是需要保密的。加密算法E和解密算法D也都是公开的。虽然解密密钥SK是由公开密钥PK决定的，但却不能根据PK计算出SK。

正是基于这种理论，1978年出现了著名的RSA算法，它通常是先生成一对RSA 密钥，其中之一是保密密钥，由用户保存；另一个为公开密钥，可对外公开，甚至可在网络服务器中注册。为减少计算量，在传送信息时，常采用传统加密方法与公开密钥加密方法相结合的方式，即信息采用改进的DES或IDEA对话密钥加密，然后使用RSA密钥加密对话密钥和信息摘要。对方收到信息后，用不同的密钥解密并可核对信息摘要。

RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现今的三十多年里，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。


RSA的算法涉及三个参数，$$$n$$$、$$$e$$$、$$$d$$$。

其中，$$$n$$$是两个大质数$$$p$$$、$$$q$$$的积，$$$n$$$的二进制表示时所占用的位数，就是所谓的密钥长度。

$$$e$$$和$$$d$$$是一对相关的值，$$$e$$$可以任意取，但要求$$$e$$$与$$$\phi(n) = (p - 1) * (q - 1)$$$互质，即$$$\gcd(e, \phi(n)) = 1$$$；再选择$$$d$$$，要求$$$(d * e) \bmod \phi(n) = 1$$$，也就是求$$$d = e ^{-1} \bmod \phi(n)$$$。

$$$(n, e)$$$, $$$(n, d)$$$就是密钥对。其中$$$(n, e)$$$为公钥，$$$(n, d)$$$为私钥。

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

$$$A = B ^ d \mod n$$$
$$$B = A ^ e \mod n$$$ （公钥加密体制中，一般用公钥加密，私钥解密）

$$$e$$$和$$$d$$$可以互换使用，即：

$$$A = B ^ e \mod n$$$
$$$B = A ^ d \mod n$$$


对于$$$e$$$选择65537可以对公钥加速计算（同时，NIST规定$$$e$$$的值不应当小于65537），以下公式：

$$$x^{65537} = x^{(2^{16} + 1)}$$$

Congruence Modulo

同余的概念是数学王子高斯（Gauss，德国）给出的。两个整数$$$a$$$，$$$b$$$，若它们除以整数$$$m$$$所得的余数相等，则称$$$a$$$，$$$b$$$对于模$$$m$$$同余,记作
$$$a\equiv b \pmod{m}$$$

Euler Phi

$$$\phi(n)=n\prod_{p|n}\left(1-\frac{1}{p}\right)$$$

Euler's theorem

$$$a^{\varphi (n)} \equiv 1 \pmod{n}$$$

Mod Inverse

同余的概念是数学王子高斯（Gauss，德国）给出的。两个整数$$$a$$$，$$$b$$$，若它们除以整数$$$m$$$所得的余数相等，则称$$$a$$$，$$$b$$$对于模$$$m$$$同余,记作 $$$a \equiv b \pmod m$$$。

  • $$$2^{-1} \bmod 7 = 4 \ \ \ \Rightarrow \ \ \ 2 \times 4 \bmod 7 = 1$$$
  • $$$3^{-1} \bmod 7 = 5 \ \ \ \Rightarrow \ \ \ 3 \times 5 \bmod 7 = 1$$$
  • $$$4^{-1} \bmod 7 = 2 \ \ \ \Rightarrow \ \ \ 4 \times 2 \bmod 7 = 1$$$
  • $$$5^{-1} \bmod 7 = 3 \ \ \ \Rightarrow \ \ \ 5 \times 3 \bmod 7 = 1$$$
  • $$$6^{-1} \bmod 7 = 6 \ \ \ \Rightarrow \ \ \ 6 \times 6 \bmod 7 = 1$$$
  • $$$7^{-1} \bmod 7 = N/A$$$


计算 $$$m^{-1} \bmod n = ?$$$

  1. 找到一个整数 $$$p$$$ 使得 $$$1/m + p = (1 + p * m)/m$$$，使得整数$$$(1 + p * m)$$$是$$$n$$$的倍数 ,也即 $$$(1 + p * m) \bmod n = 0$$$
  2. 问题转化为 $$$1/m ≡ -p \bmod n$$$,此时只要求得 $$$-p \bmod n$$$ 的值就可以了



示例：

1/3 mod 7 = ?
1/3 + 2 = 7/3
-2 mod 7 = 5
1/3 mod 7 = 5

Java Implemention

Java源代码：

package me.hatter.tests.rsa;

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

public class Rsa {

    BigInteger n, d, e;

    public Rsa(int bitlen) {
        SecureRandom r = new SecureRandom();
        BigInteger p = new BigInteger(bitlen / 2, 100, r);
        BigInteger q = new BigInteger(bitlen / 2, 100, r);
        n = p.multiply(q);
        BigInteger m = (p.subtract(BigInteger.ONE)).multiply(q.subtract(BigInteger.ONE));
        e = new BigInteger("3");
        while (m.gcd(e).intValue() > 1)
            e = e.add(new BigInteger("2"));
        d = e.modInverse(m);
    }

    public BigInteger encrypt(BigInteger message) {
        return message.modPow(e, n);
    }

    public BigInteger decrypt(BigInteger message) {
        return message.modPow(d, n);
    }
}

测试代码：

package me.hatter.tests.rsa;

import java.math.BigInteger;
import java.util.Arrays;

public class RsaTest {

    public static void main(String[] args) {
        Rsa rsa = new Rsa(100);

        System.out.println(Arrays.asList((Object) rsa.n, rsa.n.toString(2)));
        System.out.println(Arrays.asList((Object) rsa.e, rsa.e.toString(2)));
        System.out.println(Arrays.asList((Object) rsa.d, rsa.d.toString(2)));

        BigInteger secret = new BigInteger("19831127");
        BigInteger encrypted = rsa.encrypt(secret);
        BigInteger decrypted = rsa.decrypt(encrypted);

        System.out.println(Arrays.asList((Object) secret, secret.toString(2)));
        System.out.println(Arrays.asList((Object) encrypted, encrypted.toString(2)));
        System.out.println(Arrays.asList((Object) decrypted, decrypted.toString(2)));
    }
}

示例输出：

[800832607577059504508264553197, 1010000110111010000100110100111101101001110100101100111111001100000001011011011010001001101011101101]
[5, 101]
[640666086061646139257285584253, 1000000101100001101010010000110001010100101010000101001011111111101110110000100001010010010101111101]
[19831127, 1001011101001100101010111]
[604282692324973844959267916711, 111101000001000101011101101011101101011010011010001000011101000100100001100100010000000101110100111]
[19831127, 1001011101001100101010111]


Another implemention: myRSA.java

Chinese Remainder Theorem

“中国剩余定理”：给出 m 个两两互质的整数，它们的乘积为 P ；假设有一个未知数 M ，如果我们已知 M 分别除以这 m 个数所得的余数，那么在 0 到 P – 1 的范围内，我们可以唯一地确定这个 M 。这可以看作是 M 的一个特解。其他所有满足要求的 M ，则正好是那些除以 P 之后余数等于这个特解的数。

注意，除数互质的条件是必需的，否则结论就不成立了。比如说，在 0 到 7 的范围内，除以 4 余 1 并且除以 2 也余 1 的数有 2 个，除以 4 余 1 并且除以 2 余 0 的数则一个也没有。

Generate Private RSA Key

RSA Private Key format:

RSAPrivateKey ::= SEQUENCE {
  version           Version,
  modulus           INTEGER,  -- n
  publicExponent    INTEGER,  -- e
  privateExponent   INTEGER,  -- d
  prime1            INTEGER,  -- p
  prime2            INTEGER,  -- q
  exponent1         INTEGER,  -- d mod (p-1)
  exponent2         INTEGER,  -- d mod (q-1)
  coefficient       INTEGER,  -- (inverse of q) mod p
  otherPrimeInfos   OtherPrimeInfos OPTIONAL
}

package me.hatter.tests.rsa;

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

// modulus: n
// publicExponent: e
// privateExponent: d
// prime1: p
// prime2: q
// exponent1: dp
// exponent2: dq
// coefficient: qinv
//
// http://jianiau.blogspot.hk/2014/05/rsa-decrypt-with-crt.html
public class RsaCrt {

    // dp = d mod (p−1)
    // dq = d mod (q−1)
    // qinv = q^−1 mod p
    BigInteger n, d, e;
    BigInteger p, q;   // n = p * q
    BigInteger dp, dq, qinv;

    public RsaCrt(int bitlen) {
        SecureRandom r = new SecureRandom();
        BigInteger p = new BigInteger(bitlen / 2, 100, r);
        BigInteger q = new BigInteger(bitlen / 2, 100, r);
        n = p.multiply(q);
        BigInteger m = (p.subtract(BigInteger.ONE)).multiply(q.subtract(BigInteger.ONE));
        e = new BigInteger("3");
        while (m.gcd(e).intValue() > 1)
            e = e.add(new BigInteger("2"));
        d = e.modInverse(m);
        // --------------------------------------------------------------------------------
        this.p = p;
        this.q = q;
        dp = d.mod(p.subtract(BigInteger.ONE));
        dq = d.mod(q.subtract(BigInteger.ONE));
        qinv = q.modInverse(p);
    }

    public BigInteger encrypt(BigInteger message) {
        return message.modPow(e, n);
    }

    public BigInteger decrypt(BigInteger message) {
        return message.modPow(d, n);
    }
}

package me.hatter.tests.rsa;

import java.io.ByteArrayOutputStream;
import java.io.IOException;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

import me.hatter.tools.commons.shortutil.B64s;

public class RsaCrtToPem {

    static final int INTEGER     = 0x02;
    static final int SEQUENCE    = 0x10;
    static final int CONSTRUCTED = 0x20;

    public static void main(String[] args) throws Exception {

        RsaCrt rsaCrt = new RsaCrt(1024);

        printRsaCrtPem(rsaCrt);
    }

    static void printRsaCrtPem(RsaCrt rsaCrt) throws IOException {
        ByteArrayOutputStream rsaPriBaos = new ByteArrayOutputStream();

        writeInteger(rsaPriBaos, BigInteger.ZERO);
        writeInteger(rsaPriBaos, rsaCrt.n);
        writeInteger(rsaPriBaos, rsaCrt.e);
        writeInteger(rsaPriBaos, rsaCrt.d);
        writeInteger(rsaPriBaos, rsaCrt.p);
        writeInteger(rsaPriBaos, rsaCrt.q);
        writeInteger(rsaPriBaos, rsaCrt.dp);
        writeInteger(rsaPriBaos, rsaCrt.dq);
        writeInteger(rsaPriBaos, rsaCrt.qinv);
        rsaPriBaos.flush();

        byte[] rsaPriBytes = rsaPriBaos.toByteArray();
        rsaPriBaos.close();

        ByteArrayOutputStream rsaPriSeqBaos = new ByteArrayOutputStream();

        rsaPriSeqBaos.write(SEQUENCE | CONSTRUCTED);
        writeLength(rsaPriSeqBaos, rsaPriBytes.length);
        rsaPriSeqBaos.write(rsaPriBytes);
        rsaPriSeqBaos.flush();

        byte[] rsaPriSeqBytes = rsaPriSeqBaos.toByteArray();
        rsaPriSeqBaos.close();

        String b64 = B64s.normal().encode(rsaPriSeqBytes);

        System.out.println("-----BEGIN RSA PRIVATE KEY-----" //
                           + "\n" + joinStrings(splitString(b64, 64), "\n") + "\n" //
                           + "-----END RSA PRIVATE KEY-----");
    }

    static void writeInteger(ByteArrayOutputStream baos, BigInteger bigInt) throws IOException {
        byte[] bs = bigInt.toByteArray();
        baos.write(INTEGER);
        writeLength(baos, bs.length);
        baos.write(bs);
    }

    static void writeLength(ByteArrayOutputStream baos, int len) throws IOException {
        if (len > 127) {
            int size = 1;
            int val = len;

            while ((val >>>= 8) != 0) {
                size++;
            }

            baos.write(size | 0x80);

            for (int i = (size - 1) * 8; i >= 0; i -= 8) {
                baos.write((len >> i));
            }
        } else {
            baos.write(len);
        }
    }

    static String joinStrings(String[] strs, String separator) {
        if (strs == null) {
            return null;
        }
        if (strs.length == 0) {
            return "";
        }
        StringBuilder sb = new StringBuilder();
        sb.append(strs[0]);
        for (int i = 1; i < strs.length; i++) {
            sb.append(separator).append(strs[i]);
        }
        return sb.toString();
    }

    static String[] splitString(String str, int w) {
        List<String> list = new ArrayList<String>();
        while (str.length() > w) {
            list.add(str.substring(0, w));
            str = str.substring(w);
        }
        if (!str.isEmpty()) {
            list.add(str);
        }
        return list.toArray(new String[0]);
    }
}

Outputs:

-----BEGIN RSA PRIVATE KEY-----
MIICWwIBAAKBgQCvScCJF8GDeBf5ocMCVLbBK9I0lDHIdv5ZiuncnrLKdZmLWC4a
gakUX0ObnEI3VtVWbQ9lo3diBt5ZCxxxOyKK4ga9lnbzb/v+wJwDqhTjHj0Qmp+N
hSEI2miCBfEx0JizLQKnDMHxLTtjN6QKy047TnBA+2yUuyNI+5AJq+gFTwIBBQKB
gCMOwBtrJrPk0ZhTjWbdviaiXT23PSgXzHhO+5KGI8IXhRveb57mu2p5c+vsDT5E
kRFJAxRT5K00kt6b0n0L07ULPO3525Yoywg0FtloIFJUvUezLTVMrb8FRS4KtzA0
WMgrNYbChMEPBluVck/YXjiITkNcrVf60Fb2EmtPdibFAkEA6l/wmzd/ypL7iJhY
hDl25G/Wq7I8nyZUFhZTaCRWdOr2QYsgCpB+a33ajxmiQuBzz948AtiSxza+FipW
Ego1WwJBAL92Jxn1hNlx2jORbB050JIa028LRmaV+an4SGg46lXx1BNr5TWZrXad
vr1O2U6WrNUKtCkxSg3a2BcJmwyPDh0CQQCMn/bDh7MTJP1R9QHo70dV3LQAniRf
fWWm2jILSQCsjPonU3mf8EvaGE/vdcfBud8WUiQBtSTd7aVAf80+BiADAkBy4H3c
YByCd4LrvadEvEnxQ0upBsPXJsj/lPg+iIyZ938+2lZTXDTgxQwLL08vJzR/0zjl
g/k7g050OPahIqIRAkEAwu6Klg7zX9Uxhscfmpy0J1sEguJW5C3LvV9i7OnVjlqH
R+y/lLOW1hXHUTrAoVtjM60yYEZRbHrkOH7UnkLVNQ==
-----END RSA PRIVATE KEY-----

Display as text:

$ openssl rsa -in prikey.pem -text -noout
Private-Key: (1024 bit)
modulus:
    00:af:49:c0:89:17:c1:83:78:17:f9:a1:c3:02:54:
    b6:c1:2b:d2:34:94:31:c8:76:fe:59:8a:e9:dc:9e:
    b2:ca:75:99:8b:58:2e:1a:81:a9:14:5f:43:9b:9c:
    42:37:56:d5:56:6d:0f:65:a3:77:62:06:de:59:0b:
    1c:71:3b:22:8a:e2:06:bd:96:76:f3:6f:fb:fe:c0:
    9c:03:aa:14:e3:1e:3d:10:9a:9f:8d:85:21:08:da:
    68:82:05:f1:31:d0:98:b3:2d:02:a7:0c:c1:f1:2d:
    3b:63:37:a4:0a:cb:4e:3b:4e:70:40:fb:6c:94:bb:
    23:48:fb:90:09:ab:e8:05:4f
publicExponent: 5 (0x5)
privateExponent:
    23:0e:c0:1b:6b:26:b3:e4:d1:98:53:8d:66:dd:be:
    26:a2:5d:3d:b7:3d:28:17:cc:78:4e:fb:92:86:23:
    c2:17:85:1b:de:6f:9e:e6:bb:6a:79:73:eb:ec:0d:
    3e:44:91:11:49:03:14:53:e4:ad:34:92:de:9b:d2:
    7d:0b:d3:b5:0b:3c:ed:f9:db:96:28:cb:08:34:16:
    d9:68:20:52:54:bd:47:b3:2d:35:4c:ad:bf:05:45:
    2e:0a:b7:30:34:58:c8:2b:35:86:c2:84:c1:0f:06:
    5b:95:72:4f:d8:5e:38:88:4e:43:5c:ad:57:fa:d0:
    56:f6:12:6b:4f:76:26:c5
prime1:
    00:ea:5f:f0:9b:37:7f:ca:92:fb:88:98:58:84:39:
    76:e4:6f:d6:ab:b2:3c:9f:26:54:16:16:53:68:24:
    56:74:ea:f6:41:8b:20:0a:90:7e:6b:7d:da:8f:19:
    a2:42:e0:73:cf:de:3c:02:d8:92:c7:36:be:16:2a:
    56:12:0a:35:5b
prime2:
    00:bf:76:27:19:f5:84:d9:71:da:33:91:6c:1d:39:
    d0:92:1a:d3:6f:0b:46:66:95:f9:a9:f8:48:68:38:
    ea:55:f1:d4:13:6b:e5:35:99:ad:76:9d:be:bd:4e:
    d9:4e:96:ac:d5:0a:b4:29:31:4a:0d:da:d8:17:09:
    9b:0c:8f:0e:1d
exponent1:
    00:8c:9f:f6:c3:87:b3:13:24:fd:51:f5:01:e8:ef:
    47:55:dc:b4:00:9e:24:5f:7d:65:a6:da:32:0b:49:
    00:ac:8c:fa:27:53:79:9f:f0:4b:da:18:4f:ef:75:
    c7:c1:b9:df:16:52:24:01:b5:24:dd:ed:a5:40:7f:
    cd:3e:06:20:03
exponent2:
    72:e0:7d:dc:60:1c:82:77:82:eb:bd:a7:44:bc:49:
    f1:43:4b:a9:06:c3:d7:26:c8:ff:94:f8:3e:88:8c:
    99:f7:7f:3e:da:56:53:5c:34:e0:c5:0c:0b:2f:4f:
    2f:27:34:7f:d3:38:e5:83:f9:3b:83:4e:74:38:f6:
    a1:22:a2:11
coefficient:
    00:c2:ee:8a:96:0e:f3:5f:d5:31:86:c7:1f:9a:9c:
    b4:27:5b:04:82:e2:56:e4:2d:cb:bd:5f:62:ec:e9:
    d5:8e:5a:87:47:ec:bf:94:b3:96:d6:15:c7:51:3a:
    c0:a1:5b:63:33:ad:32:60:46:51:6c:7a:e4:38:7e:
    d4:9e:42:d5:35

Encrypt and Sign

RSAES-PKCS1-v1_5 & RSASSA-PKCS1-v1_5


RSAES-OAEP & RSASSA-PSS



package me.hatter.tests.rsa;

import java.io.ByteArrayOutputStream;
import java.io.IOException;
import java.math.BigInteger;
import java.security.SecureRandom;

import me.hatter.tools.commons.shortutil.B64s;

// http://www.cnblogs.com/spencerN/archive/2012/10/18/2729602.html
// http://jianiau.blogspot.hk/2014/05/rsa-pkcs1-padding.html
public class RsaEncrypt {

    // 如果使用公钥操作,BT永远为02,如果用私钥操作则可能为00或01
    static int BT_00 = 0x00;
    static int BT_01 = 0x01;
    static int BT_02 = 0x02;

    public static void main(String[] args) throws IOException {
        String message = "Hello World!!!";

        int needBitLength = 1024;
        int generateCount = 0;
        RsaCrt rsaCrt;
        do {
            System.out.println("Generate RSA key pair @ " + (generateCount++));
            rsaCrt = new RsaCrt(needBitLength);
        } while (rsaCrt.n.bitLength() != needBitLength);

        System.out.println();
        RsaCrtToPem.printRsaCrtPem(rsaCrt);

        System.out.println();
        System.out.println("Bit count of n: " + rsaCrt.n.bitLength());
        System.out.println();
        BigInteger bi = rsaCrt.encrypt(new BigInteger(pkcs1PaddingForPubKey(rsaCrt.n.bitLength(), message.getBytes())));
        System.out.println(B64s.normal().encode(bi.toByteArray()));

        System.out.println();
        BigInteger bi2 = rsaCrt.decrypt(new BigInteger(pkcs1PaddingForPriKey(rsaCrt.n.bitLength(), message.getBytes())));
        System.out.println(B64s.normal().encode(bi2.toByteArray()));
    }

    // EB = 00+ BT+PS +00 + D

    static byte[] pkcs1PaddingForPriKey(int bitLen, byte[] D) throws IOException {
        int maxLen = (bitLen / 8) - (1 + 1 + 8 + 1);
        if (D.length > maxLen) {
            // BT DO NOT use 00, so PS length is 8
            throw new RuntimeException("D is to long: " + D.length);
        }
        ByteArrayOutputStream baos = new ByteArrayOutputStream();
        baos.write(0x00);
        baos.write(BT_01);
        // PS: BT为02和01的,PS至少要有8个字节长
        int PSLen = (bitLen / 8) - D.length - (1 + 1 + 1);
        for (int i = 0; i < PSLen; i++) {
            baos.write(0xFF);
        }
        baos.write(0x00);
        baos.write(D);
        return baos.toByteArray();
    }

    static byte[] pkcs1PaddingForPubKey(int bitLen, byte[] D) throws IOException {
        int maxLen = (bitLen / 8) - (1 + 1 + 8 + 1);
        if (D.length > maxLen) {
            // BT DO NOT use 00, so PS length is 8
            throw new RuntimeException("D is to long: " + D.length);
        }
        ByteArrayOutputStream baos = new ByteArrayOutputStream();
        baos.write(0x00);
        baos.write(BT_02);
        // PS: BT为02和01的,PS至少要有8个字节长
        int PSLen = (bitLen / 8) - D.length - (1 + 1 + 1);
        SecureRandom secureRandom = new SecureRandom();
        for (int i = 0; i < PSLen; i++) {
            int randomByte = secureRandom.nextInt(0xFF - 1) + 1;
            if (randomByte <= 0 || randomByte > 0xFF) {
                throw new RuntimeException("Something wrong: " + randomByte);
            }
            baos.write(randomByte);
        }
        baos.write(0x00);
        baos.write(D);
        return baos.toByteArray();
    }
}

Outputs:

Generate RSA key pair @ 0

-----BEGIN RSA PRIVATE KEY-----
MIICWgIBAAKBgQChkURUf2LrM8Xw5pTvs5H70jhVrDwXlzhoMbHVUDSylQWqSqCI
Iq4F9UXXaoxz80/oOldv61JP/6O8D22giNSUuZYgY2YTDJXggamLYM61H7DD2tZE
PYuytLJAF7yoabSDJG+wkAwYhzuFdiyADsUD2ZCR5KPr2rmD7s1KQGPWSQIBBQKB
gCBQQN2zE8ij9GNhUPy9g5jDpN3vPzfrC0gJ8F3c11bqmruohoGgiTRkQSsVT0pj
3MgLqxZiQ6mZhyWcr4aBxB1sJmK/PAlUePcisbe6w3bE07+r+9zmdk28y1sfmaPk
3pqf2+jOPBC45+WVUp6yz2ZzIgXwQw/1EB09P2NjxT9RAkEA8bwtpXkM/7+j+Za1
oxfWrbORoMSiToulTViSnx9bn+0/GukiKxTlaYCWF5eideeCXv8WthzbDUKRqSbP
TqZB/wJBAKsaBQHA12Z5aNqaPxfljJnac94mUW6wiLdg5dqdGVFuPuo7Al3K34Ez
c3P3xBrQgTrnXX03wQQmYBNpif7jV7cCQGCxq9vKBTMZdMo8SKejIqvhbXOB2oXR
dVIjbdk/vj/4f6RdQN4IW8PNCNY8p2JcmoxmCRWlJGu0OkOpH7kPTZkCQERwzs2A
Vij9XSQ9stZb0dckLljcIJKtA3yNKL3YcIb45fdKzb8d8wB6+vsv6Aq5zUrC8jIW
TTTcJm4qNzLBVkkCQQDCitj0ABvCzmOf4+aX9zlQxfqNYl5euSrfbUPJtDH5S4o5
bJPgPbej7ELYJ25yDSk6Jes3DFbh+Qcgqe1NrKwU
-----END RSA PRIVATE KEY-----

Bit count of n: 1024

TufMBZlqFmPoVQIJ9JNmKmw5aOont3w27tzq7Rnin0uW0SmQgBBUAI1HFCY076RaOIXvOGF5HQb7rf1hkG07JbD9dXms3EdHz9coaD7ooL371lq95iYwf/MvM3zZkKzLPR4YtxVeX0qeTIrrO+z6qLzO453YElrBTsFVAy2ybKg=

dUVhLZwtiipLBZQOE2j/HvPmjEj/s8ST/LWFRSXUWGSAfBP7vSiRnkLhun1H0k26G4q08H7UmFWRZY4v/bqeXGsx6bBOHHDqGeVYcMOL5Cgl7/A5Q+YhOCChARjCtwg2YoDphZO/As/dVFbhFibaMQaXUcFJcqHx2YtgkZHDTLU=

Save RSA Private Key as prikey.pem.

Decrypt and Verify:

$ echo -n TufMBZlqFmPoVQIJ9JNmKmw5aOont3w27tzq7Rnin0uW0SmQgBBUAI1HFCY076RaOIXvOGF5HQb7rf1hkG07JbD9dXms3EdHz9coaD7ooL371lq95iYwf/MvM3zZkKzLPR4YtxVeX0qeTIrrO+z6qLzO453YElrBTsFVAy2ybKg= | base64 -D | openssl rsautl -inkey prikey.pem -decrypt
Hello World!!!

$ echo -n dUVhLZwtiipLBZQOE2j/HvPmjEj/s8ST/LWFRSXUWGSAfBP7vSiRnkLhun1H0k26G4q08H7UmFWRZY4v/bqeXGsx6bBOHHDqGeVYcMOL5Cgl7/A5Q+YhOCChARjCtwg2YoDphZO/As/dVFbhFibaMQaXUcFJcqHx2YtgkZHDTLU= | base64 -D | openssl rsautl -inkey prikey.pem -verify
Hello World!!!


Signature in Java:

package me.hatter.tests.rsa;

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.math.BigInteger;
import java.security.SecureRandom;
import java.security.interfaces.RSAPrivateCrtKey;
import java.security.interfaces.RSAPrivateKey;

import org.bouncycastle.asn1.ASN1InputStream;
import org.bouncycastle.asn1.ASN1Primitive;

import me.hatter.tools.commons.bytes.Bytes;
import me.hatter.tools.commons.security.digest.Digests;
import me.hatter.tools.commons.security.rsa.RSAKeyGeneratorUtil;
import me.hatter.tools.commons.security.rsa.RSAKeyPair;
import me.hatter.tools.commons.security.sign.Signatures;
import me.hatter.tools.commons.shortutil.Iou;
import me.hatter.tools.commons.string.StringUtil;

public class RsaSign {

    public static void main(String[] args) throws IOException {
        RSAKeyPair kp = RSAKeyGeneratorUtil.generateRsaKeyPair(2048, new SecureRandom());
        RSAPrivateKey priKey = kp.getPrivateKey();

        byte[] bs = "hello wolrd".getBytes();
        Bytes sign = Signatures.rsaSha256().key(priKey).sign(bs);

        System.out.println("SHA256: " + Digests.sha256().digest(bs).asHex());
        System.out.println("SIGNATURE: " + sign.asBase64());

        RsaCrt rsaCrt = new RsaCrt((RSAPrivateCrtKey) priKey);
        BigInteger enc = rsaCrt.encrypt(new BigInteger(1, sign.bytes()));
        System.out.println("SIGNATURE PUBKEY ENCRYPT: " + Bytes.from(enc.toByteArray()).asHex());

        String pkeHex = Bytes.from(enc.toByteArray()).asHex();
        Bytes sigDer = Bytes.fromHex(StringUtil.substringAfter(pkeHex, "00"));
        System.out.println("SIG DER: " + sigDer.asBase64());
        System.out.println("SIG ASN.1: " + toDERObject(sigDer.bytes()));
    }

    // https://stackoverflow.com/questions/2409618/how-do-i-decode-a-der-encoded-string-in-java
    static private ASN1Primitive toDERObject(byte[] data) throws IOException {
        ByteArrayInputStream inStream = new ByteArrayInputStream(data);
        ASN1InputStream asnInputStream = new ASN1InputStream(inStream);
        ASN1Primitive asn1Primitive = asnInputStream.readObject();
        Iou.closeQuietly(asnInputStream);
        return asn1Primitive;
    }
}

Outputs:

SHA256: 5643b2819cb9afb67677298ae00a612814bf028a38d83d1ba77a169b69655d2a
SIGNATURE: HTx8SP85bi0LScm5oiVCTHABWr8LYYqZLcaCbybLag6XrQsLEmbZ/PPCcee1ZTmwAyXnr3SSQqjo6MdLzL2mlOKcJ71g6vGlKzu59MROaN5zUCFgsTLS8SKmlrBdSMCeCKVp6KOvKrl++lTAn5xUq0de2/43UfnZpwcjnBKxeGbeRVXYp2mUBxGu+yBIW7FO5LP3sTwApBQ8s1aokChtiIBfIp5P2eVlyuWHr6kcgPs19JcTLi0d7DxfYvDO7STsijFDBWScgbF1uK+nu8OqVCxLclRg7BqOI6qje0SsPtI1uyEZCtSyX+aXr39Q9BdfuaUdMkLnjdUcuLh/l0LxOg==
SIGNATURE PUBKEY ENCRYPT: 01ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff003031300d0609608648016503040201050004205643b2819cb9afb67677298ae00a612814bf028a38d83d1ba77a169b69655d2a
SIG DER: MDEwDQYJYIZIAWUDBAIBBQAEIFZDsoGcua+2dncpiuAKYSgUvwKKONg9G6d6FptpZV0q
SIG ASN.1: [[2.16.840.1.101.3.4.2.1, NULL], #5643b2819cb9afb67677298ae00a612814bf028a38d83d1ba77a169b69655d2a]

Strength

在数论中，普通数域筛选法（GNFS）是已知效率最高的分解整数的算法。分解整数n需要

$$$O\left\{\exp \left[\left({64 \over 9}\log n\right)^{{1 \over 3}}(\log \log n)^{{2 \over 3}}\right]\right\}$$$

Attack

针对RSA最流行的攻击一般是基于大数因数分解。1999年，RSA-155 (512 bits)被成功分解，花了五个月时间（约8000 MIPS年）和224 CPU hours在一台有3.2G中央内存的Cray C916计算机上完成。

2002年，RSA-158也被成功因数分解。

RSA-158表示如下：

39505874583265144526419767800614481996020776460304936454139376051579355626529450683609
727842468219535093544305870490251995655335710209799226484977949442955603

= 3388495837466721394368393204672181522815830368604993048084925840555281177×
  11658823406671259903148376558383270818131012258146392600439520994131344334162924536139

2009年12月12日，编号为RSA-768（768 bits, 232 digits）数也被成功分解[1]。这一事件威胁了现通行的1024-bit密钥的安全性，普遍认为用户应尽快升级到2048-bit或以上。

RSA-768表示如下：

123018668453011775513049495838496272077285356959533479219732245215172640050726
365751874520219978646938995647494277406384592519255732630345373154826850791702
6122142913461670429214311602221240479274737794080665351419597459856902143413

= 3347807169895689878604416984821269081770479498371376856891
  2431388982883793878002287614711652531743087737814467999489×
  3674604366679959042824463379962795263227915816434308764267
  6032283815739666511279233373417143396810270092798736308917

Reference

  1. https://en.wikipedia.org/wiki/RSA_(cryptosystem)
  2. https://zh.wikipedia.org/wiki/RSA%E5%8A%A0%E5%AF%86%E6%BC%94%E7%AE%97%E6%B3%95 - RSA加密演算法
  3. http://baike.baidu.com/view/10613.htm?fromtitle=RSA%E5%8A%A0%E5%AF%86%E7%AE%97%E6%B3%95 - RSA加密算法
  4. http://pajhome.org.uk/crypt/rsa/implementation.html
  5. https://gmplib.org/
  6. http://www.gnu.org/software/gnu-crypto/
  7. http://pajhome.org.uk/crypt/rsa/contrib/myRSA.java
  8. http://www.matrix67.com/blog/archives/5100 - 跨越千年的RSA算法
  9. http://www.cnblogs.com/spencerN/archive/2012/10/18/2729602.html - PKCS #1 RSA Encryption Version 1.5
  10. http://jianiau.blogspot.hk/2014/05/rsa-pkcs1-padding.html - RSA非對稱加密演算法 (五) PKCS#1 v1.5 padding
  11. https://cryptosense.com/why-pkcs1v1-5-encryption-should-be-put-out-of-our-misery/ - Why PKCS#1v1.5 Encryption Should Be Put Out of Our Misery
  12. http://stackoverflow.com/questions/4647577/%CF%86n-p-1q-1-p-and-q-are-two-big-numbers-find-e-such-that-gcde-%CF%86n-1 - φ(n) = (p-1)(q-1) p and q are two big numbers find e such that gcd(e,φ(n)) = 1
  13. https://tools.ietf.org/html/rfc3447 - Public-Key Cryptography Standards (PKCS) #1: RSA Cryptography Specifications Version 2.1
  14. https://www.cryptopp.com/wiki/RSA_Cryptography - RSA Cryptography
  15. https://www.cryptopp.com/wiki/RSA_Encryption_Schemes
  16. https://www.cryptopp.com/wiki/RSA_Signature_Schemes
  17. http://www.di-mgt.com.au/rsa_alg.html
  18. http://www.di-mgt.com.au/crt_rsa.html - Using the CRT with RSA
  19. http://www.ruanyifeng.com/blog/2013/06/rsa_algorithm_part_one.html - RSA算法原理（一）
  20. http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html - RSA算法原理（二）
  21. https://en.wikipedia.org/wiki/General_number_field_sieve - General number field sieve