初等数论
同余定理
https://baike.baidu.com/item/%E5%90%8C%E4%BD%99%E5%AE%9A%E7%90%86/1212360
假设 b % a = 0, 则记作 a | b
以下为同余定理的性质:
欧拉函数
φ(n): 小于或等于n的正整数中与n互质的数的数目, 若n为质数, 则φ(n)等于(n - 1), 因为[1, n-1]均与 n 互质.
例如 φ(10) = 4, 其中有1, 3, 7, 9与10互质.
若m,n互质，有 φ(m * n) = φ(m) * φ(n).
以此计算φ(10) = φ(2 * 5) = φ(2) * φ(5) = (2 - 1) * (5 - 1) = 4
费马-小定理
若p为质数且a不是p的倍数, 则有 ap-1 ≡ 1 (mod p)
根据反身性有 a ≡ a (mod p) , 根据相乘性有 ap ≡ a (mod p)
乘法逆元
ab ≡ 1 (mod m) , 则称a关于1模m的乘法逆元为b, 当a与m互质时, b有解, 否则b无解.
例如
4x ≡ 1 (mod 7), 则成4关于1模7的乘法逆元为x, 显然4与7互质, 因此x有解, 利用扩展欧几里得算法可求得一个x.
4x ≡ 1 (mod 7) 等价与 7k + 1 = 4x
欧几里得与扩展欧几里得算法
欧几里得算法: gcd(a, b) = gcd(b, a % b)
利用欧几里得快速求 ax+by = gcd(a, b) 得一组解(x, y).
ax + by = gcd(a, b) = gcd(b, a % b)
= bx1 +(a % b) y1
= bx1 +(a - [a / b] * b) y1 其中 [a/b] 代表小于等于结果的最大整数, 如 [5/2] = 2
= bx1 + ay1 - [a / b] * by1
等式相等等价于系数相等, 因此有:
x = y1
y = x1 - [a / b] * y1
代码
private static class Pair {
long x, y;
}
/**
* 扩展欧几里得算法, 快速求出 ax + by = 1 的一组解(x, y), 其中a, b是已知整数.
* @param a
* @param b
* @param pair 一组解(x, y)
* @return 最大公因数 gcd(a, b)
*/
private static int gcd(int a, int b, Pair pair){
if (b == 0){
pair.x = 1;
pair.y = 0;
return 0;
}
Pair nextPair = new Pair();
int d = gcd(b, a % b, nextPair);
pair.x = nextPair.y;
pair.y = nextPair.x - a / b * nextPair.y;
if (d == 0){
return b;
}
return d;
}
RSA
生成密钥对
- 生成随机大质数 p, q , 且约定 p > q,
- 生成随机数 q , 且约定 p > q .
- 计算n = pq, φ(n) = (p - 1)(q - 1), n 又称 modulus.
- 若 n 的 bit位数大于等于 密钥所需位数, 则重复第二步.
- 通常 e 为 65537, 利用欧几里得算法计算 gcd(e, φ(n)) 结果若不为1, 即 φ(n) 与 e 不互质, 继续第一步生成新的 p 和 q .
- 计算 e 关于1模 φ(n) 的乘法逆元 d , 可利用扩展欧几里得算法, 即 BigInteger.modInverse()
- 计算 pe = d % (p - 1) , qe = d % (q - 1), pe又称dP, qe又称dQ.
- 计算 q 关于1模 p 的乘法逆元 coeff (qInv)
RSA生成密钥对源码位置: sun.security.rsa.RSAKeyPairGenerator#generateKeyPair
代码
public KeyPair generateKeyPair() {
// accommodate odd key sizes in case anybody wants to use them
int lp = (keySize + 1) >> 1;
int lq = keySize - lp;
if (random == null) {
random = JCAUtil.getSecureRandom();
}
BigInteger e = publicExponent;
while (true) {
// generate two random primes of size lp/lq
BigInteger p = BigInteger.probablePrime(lp, random);
BigInteger q, n;
do {
q = BigInteger.probablePrime(lq, random);
// convention is for p > q
if (p.compareTo(q) < 0) {
BigInteger tmp = p;
p = q;
q = tmp;
}
// modulus n = p * q
n = p.multiply(q);
// even with correctly sized p and q, there is a chance that
// n will be one bit short. re-generate the smaller prime if so
} while (n.bitLength() < keySize);
// phi = (p - 1) * (q - 1) must be relative prime to e
// otherwise RSA just won't work ;-)
BigInteger p1 = p.subtract(BigInteger.ONE);
BigInteger q1 = q.subtract(BigInteger.ONE);
BigInteger phi = p1.multiply(q1);
// generate new p and q until they work. typically
// the first try will succeed when using F4
if (e.gcd(phi).equals(BigInteger.ONE) == false) {
continue;
}
// private exponent d is the inverse of e mod phi
BigInteger d = e.modInverse(phi);
// 1st prime exponent pe = d mod (p - 1)
BigInteger pe = d.mod(p1);
// 2nd prime exponent qe = d mod (q - 1)
BigInteger qe = d.mod(q1);
// crt coefficient coeff is the inverse of q mod p
BigInteger coeff = q.modInverse(p);
try {
PublicKey publicKey = new RSAPublicKeyImpl(rsaId, n, e);
PrivateKey privateKey = new RSAPrivateCrtKeyImpl(
rsaId, n, e, d, p, q, pe, qe, coeff);
return new KeyPair(publicKey, privateKey);
} catch (InvalidKeyException exc) {
// invalid key exception only thrown for keys < 512 bit,
// will not happen here
throw new RuntimeException(exc);
}
}
}
填充
Cipher.getInstance("RSA/ECB/OAEPPadding")
-
RSA指加密算法alg
-
ECB指加密模式mode
-
OAEPPadding指填充方式pad
-
RSA的 mode 只支持ECB模式
-
RSA的pad支持NOPADDING|PKCS1PADDING|OAEPPADDING|OAEPWITHMD5ANDMGF1PADDING|OAEPWITHSHA1ANDMGF1PADDING|OAEPWITHSHA-1ANDMGF1PADDING|OAEPWITHSHA-224ANDMGF1PADDING|OAEPWITHSHA-256ANDMGF1PADDING|OAEPWITHSHA-384ANDMGF1PADDING|OAEPWITHSHA-512ANDMGF1PADDING|OAEPWITHSHA-512/224ANDMGF1PADDING|OAEPWITHSHA-512/256ANDMGF1PADDING
PS 指填充的数据
BT 块类型
D 数据
NoPadding
不填充
PKCS#1
总结几个特点:
- 0x00开头确保转成BigInteger后小于n, 因为m要对n求余, 若m>n, 那解密将得不到正确的结果
- BlockType为1代表是私钥加密操作, 2代表公钥操作
- 填充长度至少是8个字节, 以此可防止攻击者通过尝试所有可能的加密块来获取原文
- 8个字节填充, 头部一个字节, 一个字节类型, 一个字节尾部, 总共11字节, 因此明文必须小于blockSize - 11
V1.5
- PKCS#1 v1.5 padding (blocktype 1 and 2).
- 填充结果序列: 0x00 BT PS 0x00 D
- PS 的长度是 int psSize = paddedSize - 3 - data.length;
- BT= 1 时, PS 全部用0xFF填充, 例如 [0x00 0x01 0xFF 0xFF 0xFF ... 0x00 message]
- BT= 2时, PS 用非0随机数填充, 例如 [0x00 0x02 0xE1 0xA0 0xA2 ... 0x00 message]
- 将填充结果序列转成大数m
加密
- 然后利用公钥对m执行加密操作, 可得密文C.
- c = RSA.encrypt(公钥, m)
- C = c.toByteArray()
解密
- 利用私钥对C进行解密
- 将C 转成大数c
- m = RSA.decrypt(私钥, c)
- 去掉首部填充数据
代码
//https://tools.ietf.org/html/rfc8017#page-28
private byte[] padV15(byte[] data) throws BadPaddingException {
byte[] padded = new byte[paddedSize];
System.arraycopy(data, 0, padded, paddedSize - data.length,
data.length);
int psSize = paddedSize - 3 - data.length;
int k = 0;
padded[k++] = 0;
padded[k++] = (byte)type;
if (type == PAD_BLOCKTYPE_1) {
// blocktype 1: all padding bytes are 0xff
while (psSize-- > 0) {
padded[k++] = (byte)0xff;
}
} else {
// blocktype 2: padding bytes are random non-zero bytes
if (random == null) {
random = JCAUtil.getSecureRandom();
}
// generate non-zero padding bytes
// use a buffer to reduce calls to SecureRandom
while (psSize > 0) {
// extra bytes to avoid zero bytes,
// number of zero bytes <= 4 in 98% cases
// 避免生成的随机含0而需要重复取随机数, 因此取随机序列的时候多取了4个.
// 因为在98%的场景下, 随机序列含0数量小于等于4
byte[] r = new byte[psSize + 4];
random.nextBytes(r);
for (int i = 0; i < r.length && psSize > 0; i++) {
if (r[i] != 0) {
padded[k++] = r[i];
psSize--;
}
}
}
}
return padded;
}
V2.0 (OAEP)
代码
/**
* PKCS#1 v2.0 OAEP padding (MGF1).
* Paragraph references refer to PKCS#1 v2.1 (June 14, 2002)
*/
private byte[] padOAEP(byte[] M) throws BadPaddingException {
if (random == null) {
random = JCAUtil.getSecureRandom();
}
int hLen = lHash.length;
// 2.d: generate a random octet string seed of length hLen
// if necessary
byte[] seed = new byte[hLen];
random.nextBytes(seed);
// buffer for encoded message EM
byte[] EM = new byte[paddedSize];
// start and length of seed (as index into EM)
int seedStart = 1;
int seedLen = hLen;
// copy seed into EM
System.arraycopy(seed, 0, EM, seedStart, seedLen);
// start and length of data block DB in EM
// we place it inside of EM to reduce copying
int dbStart = hLen + 1;
int dbLen = EM.length - dbStart;
// start of message M in EM
int mStart = paddedSize - M.length;
// build DB
// 2.b: Concatenate lHash, PS, a single octet with hexadecimal value
// 0x01, and the message M to form a data block DB of length
// k - hLen -1 octets as DB = lHash || PS || 0x01 || M
// (note that PS is all zeros)
System.arraycopy(lHash, 0, EM, dbStart, hLen);
EM[mStart - 1] = 1;
System.arraycopy(M, 0, EM, mStart, M.length);
// produce maskedDB
mgf.generateAndXor(EM, seedStart, seedLen, dbLen, EM, dbStart);
// produce maskSeed
mgf.generateAndXor(EM, dbStart, dbLen, seedLen, EM, seedStart);
return EM;
}
PKCS#5
PKCS#7
加密
BigInteger.modPow(e, m): thise % m
代码
/**
* RSA private key operations with CRT. Algorithm and variable naming
* are taken from PKCS#1 v2.1, section 5.1.2.
*/
private static byte[] crtCrypt(byte[] msg, RSAPrivateCrtKey key,
boolean verify) throws BadPaddingException {
BigInteger n = key.getModulus();
BigInteger c0 = parseMsg(msg, n);
BigInteger c = c0;
BigInteger p = key.getPrimeP();
BigInteger q = key.getPrimeQ();
BigInteger dP = key.getPrimeExponentP();
BigInteger dQ = key.getPrimeExponentQ();
BigInteger qInv = key.getCrtCoefficient();
BigInteger e = key.getPublicExponent();
BigInteger d = key.getPrivateExponent();
BlindingRandomPair brp;
if (ENABLE_BLINDING) {
brp = getBlindingRandomPair(e, d, n);
c = c.multiply(brp.u).mod(n);
}
// m1 = c ^ dP mod p
BigInteger m1 = c.modPow(dP, p);
// m2 = c ^ dQ mod q
BigInteger m2 = c.modPow(dQ, q);
// h = (m1 - m2) * qInv mod p
BigInteger mtmp = m1.subtract(m2);
if (mtmp.signum() < 0) {
mtmp = mtmp.add(p);
}
BigInteger h = mtmp.multiply(qInv).mod(p);
// m = m2 + q * h
BigInteger m = h.multiply(q).add(m2);
if (ENABLE_BLINDING) {
m = m.multiply(brp.v).mod(n);
}
if (verify && !c0.equals(m.modPow(e, n))) {
throw new BadPaddingException("RSA private key operation failed");
}
return toByteArray(m, getByteLength(n));
}
解密
代码
/**
* RSA public key ops. Simple modPow().
*/
private static byte[] crypt(byte[] msg, BigInteger n, BigInteger exp)
throws BadPaddingException {
BigInteger m = parseMsg(msg, n);
BigInteger c = m.modPow(exp, n);
return toByteArray(c, getByteLength(n));
}
扩展 - 密钥格式
公钥格式
代码
RSAPublicKey ::= SEQUENCE {
modulus INTEGER, -- n
publicExponent INTEGER -- e
}
私钥格式
代码
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
}
公钥手拆
代码
30
81
9F
30
0D
06 // typeId = DerValue.tag_ObjectId
09 // lenByte = 9
2A 86 48 86 F7 0D 01 01 01 // AlgorithmId
05 // TAG = DerValue.tag_Null
00
03 // TAG = DerValue.tag_BitString
81
8D // length = 141
// length --; length = 140
00 // excessBits; 多余的bit
// validBits = length * 8 - excessBits, 有效的bit
30
81
89
02 // DerValue.tag_Integer
81
81
00 CB 20 AA CB 0A 04 79 78 90 37 53 B4 FE 8C 4E
1A C9 AE 7B 6F 69 24 39 7A E1 F1 E5 4B 55 8C 94
A6 A9 67 44 6D 6F 3A 35 FD 79 30 34 63 09 0C BE
A9 08 A2 AD 46 2C 07 CD A5 09 6B D2 4B 9D F9 01
99 B7 DD FD 59 BA E0 49 B2 5B 64 77 1E FE 05 1B
AA E9 8F 05 DC F5 AE D0 07 12 AA 66 1A 54 BD CB
35 7E DF B2 78 13 69 91 1A 17 27 F6 33 7B 1D 24
F4 59 F6 7D 97 48 82 94 C2 8C B7 72 CE 08 10 A4
29 // n
02
03
01 00 01 // e = 65537
私钥手拆
代码
30 //TAG
82 // 长度标志,若大于等于0x80, 则长度字节数为 [标志 & 0x7F], 结果必须是[0-3]; 若标志小于128, 则长度字节数为标志值.代码位于 sun.security.util.DerInputStream#getLength(int, java.io.InputStream)
02 78 // 0x82 & 0x7F = 2 因此长度为2字节
02 // DerValue.tag_Integer
01 // 长度标志 长度为1
00 // 值 PKCS8Key.version
30 // TAG = DerValue.tag_Sequence
0D // lenByte = 13
06 // typeId = DerValue.tag_ObjectId
09 //lenByte = 9
2A 86 48 86 F7 0D 01 01 01
05 // TAG = DerValue.tag_Null
00
04 // TAG = DerValue.tag_OctetString
82 // lenByte = [0x82 & 0x7F] = 2
02 62 // len = 610
// 下面是PKCS8Key格式的密钥
30 //TAG
82 // lenByte = 2
02 5E // len = 606
02 // DerValue.tag_Integer
01 // lenByte
00 // version = 0
02
81
81
00 CB 20 AA CB 0A 04 79 78 90 37 53 B4 FE 8C 4E
1A C9 AE 7B 6F 69 24 39 7A E1 F1 E5 4B 55 8C 94
A6 A9 67 44 6D 6F 3A 35 FD 79 30 34 63 09 0C BE
A9 08 A2 AD 46 2C 07 CD A5 09 6B D2 4B 9D F9 01
99 B7 DD FD 59 BA E0 49 B2 5B 64 77 1E FE 05 1B
AA E9 8F 05 DC F5 AE D0 07 12 AA 66 1A 54 BD CB
35 7E DF B2 78 13 69 91 1A 17 27 F6 33 7B 1D 24
F4 59 F6 7D 97 48 82 94 C2 8C B7 72 CE 08 10 A4
29 // n
02
03
01 00 01 // e = 65537
02
81
80
69 80 6B 15 0F FB E8 F7 74 B8 37 D2 DF 0F 12 96
19 40 75 BE 14 F7 0A 9F C7 70 F3 2E 20 9D E6 AB
75 7B 3C 70 36 80 1E 80 AB 8C 1C F9 7F 3E CE 5C
4F 2E E7 1E 76 4A 0B 46 77 D1 37 A5 AC C4 23 4E
BD 24 46 F7 36 21 6C AD 7F 3C 0E FA 62 61 BD 7C
B6 43 3C D4 39 96 02 E4 8D EA 9E 6D 7C 59 59 67
F1 84 48 0C 1D 8A 43 C3 07 C3 75 81 64 C9 BF 6A
02 04 C6 F6 8D AB 7C D8 8A 27 91 19 98 3E C0 1D // d
02
41
00 F7 6E B5 D3 3B 11 3E E3 72 F7 B2 EB 0C 6E 45
26 0C 4F 66 D6 3F D4 3C 36 14 B8 A2 EF 05 AB BD
87 8F 11 74 3C 34 D0 99 78 6C 88 49 E4 DC FF 01
B0 10 5E E2 E9 60 CF 8B BB B8 9B F8 A6 DE 14 15
B3 // p
02
41
00 D2 29 3A E1 18 0A 2A 20 18 6E F2 22 F3 98 A8
B2 F0 3F 14 3A 05 85 0C 25 09 C5 F5 6F F3 E7 A1
6A 60 CB D5 0B 91 0E 2D 2D 62 39 97 68 6F 2D EF
FA 11 B1 1B 7A 50 B4 49 8F F4 7B C7 65 D3 18 A8
B3 // q
02
41
00 A6 71 ED 12 59 2B B2 B8 62 80 49 F5 5F F9 55
BE D0 8D 21 4A 82 C9 8C 6F 7C E4 EF 86 06 B4 8E
DC 7F DB 67 EB 90 43 BA D9 8D 78 E8 EC 71 D5 81
17 25 0C 0F 6C 9A D9 42 D0 56 D1 65 25 2B 43 2B
8D // pe
02
41
00 88 EE 7E 43 9D 93 39 E1 51 AA 30 30 5F C1 AE
E1 70 31 D9 6E F8 9B B8 CF 05 30 2B 7B F7 52 8B
D4 B1 1E FE 40 1C 12 3D 93 5D 75 A2 D6 53 E2 7D
82 D5 36 2D 6E 23 D9 64 38 DC 96 2D D4 85 97 82
8B // qe
02 41
00 B1 FD 9E F6 C7 4F AB 45 20 15 DA 55 4C 15 A3
B1 7B 0A 01 F3 E9 D3 84 6A FA 5E DA 48 F1 D2 25
F5 FE C2 D2 76 52 EB A2 AA 0A 91 00 8E 3B D7 9F
01 F1 88 CB 7E 27 5C 17 78 23 95 CC 8D 41 89 4B
A2 // coeff
ABOUT ME
