パスワードを忘れた? アカウント作成
14197814 journal
プログラミング

iidaの日記: 3重素数RSA私有鍵 2

日記 by iida

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-----

typodupeerror

日々是ハック也 -- あるハードコアバイナリアン

読み込み中...