1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
|
/**
* @license
* Copyright 2016 Google Inc. All rights reserved.
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package com.google.security.wycheproof;
import java.math.BigInteger;
import java.security.KeyFactory;
import java.security.KeyPair;
import java.security.KeyPairGenerator;
import java.security.interfaces.RSAPrivateCrtKey;
import java.security.interfaces.RSAPrivateKey;
import java.security.interfaces.RSAPublicKey;
import java.security.spec.X509EncodedKeySpec;
import junit.framework.TestCase;
/**
* Tests RSA keys. Signatures and encryption are tested in different tests.
*
* @author bleichen@google.com (Daniel Bleichenbacher)
*/
// TODO(bleichen):
// - Add checks for bad random numbers
// - expect keys with e=1 to be rejected
// - expect keys with e=0 to be rejected
// - document stuff
// - Maybe also check encodings of private keys.
// - Test multi prime RSA
// - Tests for alternative representations:
// many libraries sort the primes as: p > q (but not all)
// some libraries compute d mod lambda(n)
// paramaters p,q,... are not really required
// - checks for bad random number generation
public class RsaKeyTest extends TestCase {
public static final String ENCODED_PUBLIC_KEY =
"30819f300d06092a864886f70d010101050003818d0030818902818100ab9014"
+ "dc47d44b6d260fc1fef9ab022042fd9566e9d7b60c54100cb6e1d4edc9859046"
+ "7d0502c17fce69d00ac5efb40b2cb167d8a44ab93d73c4d0f109fb5a26c2f882"
+ "3236ff517cf84412e173679cfae42e043b6fec81f9d984b562517e6febe1f722"
+ "95dbc3fdfc19d3240aa75515563f31dad83563f3a315acf9a0b351a23f020301"
+ "0001";
private void checkPrivateCrtKey(RSAPrivateCrtKey key, int expectedKeySize) throws Exception {
BigInteger p = key.getPrimeP();
BigInteger q = key.getPrimeQ();
BigInteger n = key.getModulus();
BigInteger e = key.getPublicExponent();
BigInteger d = key.getPrivateExponent();
BigInteger dp = key.getPrimeExponentP();
BigInteger dq = key.getPrimeExponentQ();
BigInteger crtCoeff = key.getCrtCoefficient();
// Simple test that (n,d,e) is a valid RSA key.
assertEquals(n, p.multiply(q));
assertEquals(expectedKeySize, n.bitLength());
int certainty = 80;
assertTrue(p.isProbablePrime(certainty));
assertTrue(q.isProbablePrime(certainty));
// Very simple checks for weak random number generators.
RandomUtil.checkPrime(p);
RandomUtil.checkPrime(q);
assertTrue(d.bitLength() > expectedKeySize / 2);
// TODO(bleichen): Keys that are very imbalanced can be broken with elliptic curve factoring.
// Add other checks. E.g. for the size of dp and dq
assertTrue(p.bitLength() > 256);
assertTrue(q.bitLength() > 256);
BigInteger p1 = p.subtract(BigInteger.ONE);
BigInteger q1 = q.subtract(BigInteger.ONE);
BigInteger phi = p1.multiply(q1);
BigInteger order = phi.divide(p1.gcd(q1)); // maximal order of elements
assertEquals(BigInteger.ONE, d.multiply(e).mod(order));
assertEquals(d.mod(p1), dp.mod(p1));
assertEquals(d.mod(q1), dq.mod(q1));
assertEquals(q.multiply(crtCoeff).mod(p), BigInteger.ONE);
}
private void checkPublicKey(RSAPublicKey pub, RSAPrivateKey priv) {
assertEquals(pub.getModulus(), priv.getModulus());
BigInteger e = pub.getPublicExponent();
// Checks that e > 1. [CVE-1999-1444]
assertEquals(e.compareTo(BigInteger.ONE), 1);
}
private void checkKeyPair(KeyPair keypair, int keySizeInBits) throws Exception {
RSAPublicKey pub = (RSAPublicKey) keypair.getPublic();
RSAPrivateKey priv = (RSAPrivateKey) keypair.getPrivate();
if (priv instanceof RSAPrivateCrtKey) {
checkPrivateCrtKey((RSAPrivateCrtKey) priv, keySizeInBits);
} else {
// Using a CRT key leads to 6-7 times better performance than not using the CRT.
// Such a perfomance loss makes a library almost useless. Thus we consider this
// a bug.
fail("Expecting an RSAPrivateCrtKey instead of " + priv.getClass().getName());
}
checkPublicKey(pub, priv);
}
public void testKeyGenerationSize(int keySizeInBits) throws Exception {
KeyPairGenerator keyGen = KeyPairGenerator.getInstance("RSA");
keyGen.initialize(keySizeInBits);
KeyPair keypair = keyGen.genKeyPair();
checkKeyPair(keypair, keySizeInBits);
}
public void testKeyGeneration() throws Exception {
testKeyGenerationSize(1024);
testKeyGenerationSize(2048);
}
/**
* Checks whether decoding and again encoding an RSA public key results
* in the same encoding.
* This is a regression test. Failing this test implies that the encoding has changed.
* Such a failure does not need to be a bug, since several encoding for the same key are
* possible.
*/
public void testEncodeDecodePublic() throws Exception {
KeyFactory kf = KeyFactory.getInstance("RSA");
byte[] encoded = TestUtil.hexToBytes(ENCODED_PUBLIC_KEY);
X509EncodedKeySpec spec = new X509EncodedKeySpec(encoded);
RSAPublicKey pub = (RSAPublicKey) kf.generatePublic(spec);
assertEquals("The test assumes that the public key is in X.509 format",
"X.509", pub.getFormat());
assertEquals(ENCODED_PUBLIC_KEY, TestUtil.bytesToHex(pub.getEncoded()));
}
}
|
