iidaの日記: 3重素数RSA私有鍵 2
3つの素数と公開指数から3重素数RSA私有鍵をつくるJavaプログラムを書いてみた。
ASN.1符号化やPEM形式への変換はBouncyCastleによる。
import org.bouncycastle.asn1.ASN1Integer;
import org.bouncycastle.asn1.ASN1Encodable;
import org.bouncycastle.asn1.DERSequence;
import org.bouncycastle.util.io.pem.PemObject;
import org.bouncycastle.util.io.pem.PemWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.math.BigInteger;
class GenRSA1 {
private static boolean isEven(BigInteger x) {
return (x != null && !x.testBit(0));
}
private static boolean isOdd(BigInteger x) {
return (x != null && x.testBit(0));
}
private static void exit(int status) {
System.exit(status);
}
private static final BigInteger ZERO = BigInteger.ZERO;
private static final BigInteger ONE = BigInteger.ONE;
private static BigInteger
extBinEuclid(BigInteger u, BigInteger v) {
BigInteger k = ONE;
while (isEven(u) && isEven(v)) {
u = u.shiftRight(1);
v = v.shiftRight(1);
k = k.shiftLeft(1);
}
BigInteger a = ONE;
BigInteger b = ZERO;
BigInteger g = u;
BigInteger ta = v;
BigInteger tb = u.subtract(ONE);
BigInteger tg = v;
do {
do {
if (isEven(g)) {
if (isOdd(a) || isOdd(b)) {
a = a.add(v);
b = b.add(u);
}
a = a.shiftRight(1);
b = b.shiftRight(1);
g = g.shiftRight(1);
}
if (isEven(tg) || g.compareTo(tg) < 0) {
BigInteger t;
t = a; a = ta; ta = t; // swap a, ta
t = b; b = tb; tb = t; // swap b, tb
t = g; g = tg; tg = t; // swap g, tg
}
} while (isEven(g));
while (a.compareTo(ta) < 0 || b.compareTo(tb) < 0) {
a = a.add(v);
b = b.add(u);
}
a = a.subtract(ta);
b = b.subtract(tb);
g = g.subtract(tg);
} while (0 < tg.signum());
while (v.compareTo(a) < 0 && u.compareTo(b) < 0) {
a = a.subtract(v);
b = b.subtract(u);
}
b = b.multiply(k);
return (g.equals(ONE)? u.subtract(b): null);
}
private static void eprintln(Object o) {
System.err.println(o);
}
private static void println(Object o) {
System.out.println(o);
}
public static void main(String[] args) {
if (args.length < 4) {
eprintln("Usage: p q e r");
exit(-1);
}
int i = 0;
String sp = args[i++];
String sq = args[i++];
String se = args[i++];
String sr = args[i++];
BigInteger p = null;
BigInteger q = null;
BigInteger e = null;
BigInteger r = null;
try {
p = new BigInteger(sp);
q = new BigInteger(sq);
e = new BigInteger(se);
r = new BigInteger(sr);
}
catch (NumberFormatException nfe) {
nfe.printStackTrace(System.err);
exit(12);
return;
}
for (BigInteger bi: new BigInteger[] { p, q, e, r }) {
if (bi.signum() < 1) {
eprintln(bi.toString() + ": NOT postive!");
exit(13);
}
}
for (BigInteger bi: new BigInteger[] { p, q, r }) {
if (!bi.isProbablePrime(10)) {
eprintln(bi.toString() + ": NOT a prime!");
exit(14);
}
}
if (p.compareTo(q) < 0) {
BigInteger t = p; p = q; q = t; // swap p, q
}
BigInteger m = p.multiply(q).multiply(r);
BigInteger n = p.subtract(ONE).multiply(q.subtract(ONE)).multiply(r.subtract(ONE));
if (ZERO.equals(n.mod(e))) {
eprintln(e.toString() + " divides " + n.toString() + "!");
exit(7);
}
BigInteger d = extBinEuclid(n, e);
if (d == null) {
eprintln(e.toString() + " divides " + n.toString() + "?");
exit(6);
}
BigInteger x1 = d.mod(p.subtract(ONE));
BigInteger x2 = d.mod(q.subtract(ONE));
BigInteger c = extBinEuclid(p, q);
BigInteger[] bia = {
ONE, m, e, d, p, q, x1, x2, (c == null? ZERO: c)
};
BigInteger[] opi = {
r, d.mod(r.subtract(ONE)), extBinEuclid(r, p.multiply(q))
};
ASN1Encodable[] ae12 = new ASN1Encodable[bia.length + 1];
ASN1Encodable[] ae3 = new ASN1Encodable[3];
{
i = 0;
for (BigInteger bi: opi) {
ae3[i++] = new ASN1Integer(bi);
}
i = 0;
for (BigInteger bi: bia) {
ae12[i++] = new ASN1Integer(bi);
}
ae12[i++] = new DERSequence(new DERSequence(ae3));
}
try {
byte[] bytes = new DERSequence(ae12).getEncoded();
PemObject po = new PemObject("RSA PRIVATE KEY", bytes);
PemWriter pw = new PemWriter(new OutputStreamWriter(System.out));
pw.writeObject(po);
pw.flush();
}
catch (IOException ioe) {
ioe.printStackTrace(System.err);
}
}
}
OpenSSLではinvalid multi prime keyと怒られることがある。
$ java GenRSA1 5 11 3 17 | openssl rsa -check
RSA key error: invalid multi prime key
writing RSA key
-----BEGIN RSA PRIVATE KEY-----
MCoCAQECAgOnAgEDAgIBqwIBCwIBBQIBBwIBAwIBCTALMAkCARECAQsCAQ0=
-----END RSA PRIVATE KEY-----
おっ、個人的にタイムリーなネタ (スコア:1)
ちょうど昨日仕事でRSA鍵を生成したり形式を変換したりしながら、『これ3つの素数で鍵を作ったらどうなるんだろう?』って思ってたところだ。
The Evolution of a Programmer (スコア:0)
https://www.ariel.com.au/jokes/The_Evolution_of_a_Programmer.html [ariel.com.au]
Master Programmer ぐらいですかね?頑張ってください!