CAVP 서비스 만들면서 작성한 RSA 키쌍 유효성 판별 코드.
문서 찾아보고 그대로 작성했을 뿐, 아직 누구에게 확인받아 본 적은 없다...
//#region RSA 키쌍의 유효성 판별
// NIST SP 800-56B r2
// (https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Br2.pdf)
// - 6.4.1.2.2 rsakpv1-prime-factor
public void verifyRsaKey(int bitLen, BigInteger e, BigInteger p, BigInteger q, BigInteger n, BigInteger d) {
if (!n.equals(p.multiply(q))) {
throw new InvalidArgumentException("n != p * q");
}
if (n.bitLength() != bitLen) {
throw new InvalidArgumentException("n 의 키 길이 != " + n.bitLength());
}
checkPrimeFactors(bitLen, e, p, q);
checkPrivateExponent(bitLen, e, p, q, d);
}
private void checkPrimeFactors(int bitLen, BigInteger e, BigInteger p, BigInteger q) {
// a. If (p < (root(2) * (2^(bitLen/2−1))) or (p > 2^(bitLen/2) – 1)
if (!checkPrimeRange(bitLen, p)) {
throw new InvalidArgumentException("p(p1) 가 유효한 범위 내에 있지 않습니다");
}
// b. If (q < (root(2) * (2^(bitLen/2−1))) or (q > 2^(bitLen/2) – 1)
if (!checkPrimeRange(bitLen, q)) {
throw new InvalidArgumentException("q(p2) 가 유효한 범위 내에 있지 않습니다");
}
// c. If |p – q| <= 2(nBits/2−100)
BigInteger difference = BigInteger.valueOf(2L * (bitLen / 2 - 100));
if (p.subtract(q).abs().compareTo(difference) <= 0) {
throw new InvalidArgumentException("|p - q| 가 너무 작습니다");
}
// d. If GCD (p – 1, epub) != 1
if (!p.subtract(BigInteger.ONE).gcd(e).equals(BigInteger.ONE)) {
throw new InvalidArgumentException("GCD(p-1, e) != 1");
}
// e. If GCD (q – 1, epub) != 1
if (!q.subtract(BigInteger.ONE).gcd(e).equals(BigInteger.ONE)) {
throw new InvalidArgumentException("GCD(q-1, e) != 1");
}
// FIPS 186-5 (https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-5.pdf)
// - Appendix B.3 Probabilistic Primality Tests
if (!p.isProbablePrime(44)) {
throw new InvalidArgumentException("p(p1) 가 소수가 아닙니다 (확률적 소수 판별법)");
}
if (!q.isProbablePrime(44)) {
throw new InvalidArgumentException("q(p2) 가 소수가 아닙니다 (확률적 소수 판별법)");
}
}
private void checkPrivateExponent(int bitLen, BigInteger e, BigInteger p, BigInteger q, BigInteger d) {
if (d.compareTo(BigInteger.valueOf(2).pow(bitLen / 2)) <= 0) {
throw new InvalidArgumentException(String.format("d(s) 가 2 ^ (%d / 2) 보다 작습니다", bitLen));
}
BigInteger pSub1 = p.subtract(BigInteger.ONE);
BigInteger qSub1 = q.subtract(BigInteger.ONE);
BigInteger gcdSub1 = pSub1.gcd(qSub1);
BigInteger lcmSub1 = pSub1.multiply(qSub1).divide(gcdSub1);
if (d.compareTo(lcmSub1) >= 0) {
// NOTE(jyha) : d 가 작을수록 공격자가 비밀키를 계산하는데 어려워지기 때문에 d < LCM(p-1, q-1) 를 유지하는 것이 좋긴 하지만,
// 일반적으로 키쌍을 생성할 때 d 의 크기까지 확인하지는 않음.
}
if (!d.multiply(e).mod(lcmSub1).equals(BigInteger.ONE)) {
throw new InvalidArgumentException("(d * e) mod LCM (p-1, q-1) != 1");
}
}
private boolean checkPrimeRange(int bitLen, BigInteger prime) {
double doubleNum = 2 ^ (bitLen / 2 - 1);
// (p < (root(2) * (2^(bitLen/2−1))) => false
if (prime.compareTo(BigInteger.valueOf((long)(Math.sqrt(2) * doubleNum))) < 0) {
return false;
}
// p > 2^(bitLen/2) – 1 => false
return prime.compareTo(BigInteger.valueOf(2).pow(bitLen / 2).subtract(BigInteger.ONE)) <= 0;
}
//#endregion
