JAVA 58
DeterministicDSA.java Guest on 22nd June 2020 03:33:12 AM
  1. package org.ietf;
  2.  
  3.    // ==================================================================
  4.  
  5.    import java.math.BigInteger;
  6.    import java.security.InvalidKeyException;
  7.    import java.security.MessageDigest;
  8.    import java.security.NoSuchAlgorithmException;
  9.    import javax.crypto.Mac;
  10.    import javax.crypto.spec.SecretKeySpec;
  11.  
  12.    /**
  13.     * <p>Deterministic DSA signature generation. This is a sample
  14.     * implementation designed to illustrate how deterministic DSA
  15.     * chooses the pseudo-random value k when signing a given message.
  16.     * This implementation was NOT optimized or hardened against
  17.     * side-channel leaks.</p>
  18.     *
  19.     * <p>An instance is created with a hash function name, which must be
  20.     * supported by the underlying Java virtual machine ("SHA-1" and
  21.     * "SHA-256" should work everywhere). The data to sign is input
  22.     * through the {@code update()} methods. The private key is set with
  23.     * {@link #setPrivateKey}. The signature is obtained by calling
  24.     * {@link #sign}; alternatively, {@link #signHash} can be used to
  25.     * sign some data which has been externally hashed. The private key
  26.     * MUST be set before generating the signature itself, but message
  27.     * data can be input before setting the key.</p>
  28.     *
  29.     * <p>Instances are NOT thread-safe. However, once a signature has
  30.     * been generated, the same instance can be used again for another
  31.     * signature; {@link #setPrivateKey} needs not be called again if the
  32.     * private key has not changed. {@link #reset} can also be called to
  33.     * cancel previously input data. Generating a signature with {@link
  34.     * #sign} (not {@link #signHash}) also implicitely causes a
  35.     * reset.</p>
  36.     *
  37.     * <pre>
  38.     * ------------------------------------------------------------------
  39.     * (c) Thomas Pornin 2011. This software is provided 'as-is', without
  40.     * any express or implied warranty. In no event will the authors be
  41.     * held liable for any damages arising from the use of this software.
  42.     *
  43.     * Permission is granted to anyone to use this software for any
  44.     * purpose, including commercial applications, and to alter it and
  45.     * redistribute it freely, subject to no restriction.
  46.     *
  47.     * Technical remarks and questions can be addressed to:
  48.     * ------------------------------------------------------------------
  49.     * </pre>
  50.     */
  51.  
  52.    public class DeterministicDSA {
  53.  
  54.            private String macName;
  55.            private MessageDigest dig;
  56.            private Mac hmac;
  57.            private BigInteger p, q, g, x;
  58.            private int qlen, rlen, rolen, holen;
  59.            private byte[] bx;
  60.  
  61.            /**
  62.             * Create an instance, using the specified hash function. The
  63.             * name is used to obtain from the JVM an implementation of
  64.             * the hash function, and an implementation of HMAC.
  65.             *
  66.             * @param hashName   the hash function name
  67.             * @throws IllegalArgumentException  on unsupported name
  68.             */
  69.            public DeterministicDSA(String hashName)
  70.            {
  71.                    try {
  72.                            dig = MessageDigest.getInstance(hashName);
  73.                    } catch (NoSuchAlgorithmException nsae) {
  74.                            throw new IllegalArgumentException(nsae);
  75.                    }
  76.                    if (hashName.indexOf('-') < 0) {
  77.                            macName = "Hmac" + hashName;
  78.                    } else {
  79.                            StringBuilder sb = new StringBuilder();
  80.                            sb.append("Hmac");
  81.                            int n = hashName.length();
  82.                            for (int i = 0; i < n; i ++) {
  83.                                    char c = hashName.charAt(i);
  84.                                    if (c != '-') {
  85.                                            sb.append(c);
  86.                                    }
  87.                            }
  88.                            macName = sb.toString();
  89.                    }
  90.                    try {
  91.                            hmac = Mac.getInstance(macName);
  92.                    } catch (NoSuchAlgorithmException nsae) {
  93.                            throw new IllegalArgumentException(nsae);
  94.                    }
  95.                    holen = hmac.getMacLength();
  96.            }
  97.  
  98.            /**
  99.             * Set the private key.
  100.             *
  101.             * @param p   key parameter: field modulus
  102.             * @param q   key parameter: sub-group order
  103.             * @param g   key parameter: generator
  104.             * @param x   private key
  105.             */
  106.            public void setPrivateKey(BigInteger p, BigInteger q,
  107.                    BigInteger g, BigInteger x)
  108.            {
  109.                    /*
  110.                     * Perform some basic sanity checks. We do not
  111.                     * check primality of p or q because that would
  112.                     * be too expensive.
  113.                     *
  114.                     * We reject keys where q is longer than 999 bits,
  115.                     * because it would complicate signature encoding.
  116.                     * Normal DSA keys do not have a q longer than 256
  117.                     * bits anyway.
  118.                     */
  119.                    if (p == null || q == null || g == null || x == null
  120.                            || p.signum() <= 0 || q.signum() <= 0
  121.                            || g.signum() <= 0 || x.signum() <= 0
  122.                            || x.compareTo(q) >= 0 || q.compareTo(p) >= 0
  123.                            || q.bitLength() > 999
  124.                            || g.compareTo(p) >= 0 || g.bitLength() == 1
  125.                            || g.modPow(q, p).bitLength() != 1) {
  126.                            throw new IllegalArgumentException(
  127.                                    "invalid DSA private key");
  128.                    }
  129.                    this.p = p;
  130.                    this.q = q;
  131.                    this.g = g;
  132.                    this.x = x;
  133.                    qlen = q.bitLength();
  134.                    if (q.signum() <= 0 || qlen < 8) {
  135.                            throw new IllegalArgumentException(
  136.                                    "bad group order: " + q);
  137.                    }
  138.                    rolen = (qlen + 7) >>> 3;
  139.                    rlen = rolen * 8;
  140.  
  141.                    /*
  142.                     * Convert the private exponent (x) into a sequence
  143.                     * of octets.
  144.                     */
  145.                    bx = int2octets(x);
  146.            }
  147.  
  148.            private BigInteger bits2int(byte[] in)
  149.            {
  150.                    BigInteger v = new BigInteger(1, in);
  151.                    int vlen = in.length * 8;
  152.                    if (vlen > qlen) {
  153.                            v = v.shiftRight(vlen - qlen);
  154.                    }
  155.                    return v;
  156.            }
  157.  
  158.            private byte[] int2octets(BigInteger v)
  159.            {
  160.                    byte[] out = v.toByteArray();
  161.                    if (out.length < rolen) {
  162.                            byte[] out2 = new byte[rolen];
  163.                            System.arraycopy(out, 0,
  164.                                    out2, rolen - out.length,
  165.                                    out.length);
  166.                            return out2;
  167.                    } else if (out.length > rolen) {
  168.                            byte[] out2 = new byte[rolen];
  169.                            System.arraycopy(out, out.length - rolen,
  170.                                    out2, 0, rolen);
  171.                            return out2;
  172.                    } else {
  173.                            return out;
  174.                    }
  175.            }
  176.  
  177.            private byte[] bits2octets(byte[] in)
  178.            {
  179.                    BigInteger z1 = bits2int(in);
  180.                    BigInteger z2 = z1.subtract(q);
  181.                    return int2octets(z2.signum() < 0 ? z1 : z2);
  182.            }
  183.  
  184.            /**
  185.             * Set (or reset) the secret key used for HMAC.
  186.             *
  187.             * @param K   the new secret key
  188.             */
  189.            private void setHmacKey(byte[] K)
  190.            {
  191.                    try {
  192.                            hmac.init(new SecretKeySpec(K, macName));
  193.                    } catch (InvalidKeyException ike) {
  194.                            throw new IllegalArgumentException(ike);
  195.                    }
  196.            }
  197.  
  198.            /**
  199.             * Compute the pseudo-random k for signature generation,
  200.             * using the process specified for deterministic DSA.
  201.             *
  202.             * @param h1   the hashed message
  203.             * @return  the pseudo-random k to use
  204.             */
  205.            private BigInteger computek(byte[] h1)
  206.            {
  207.                    /*
  208.                     * Convert hash value into an appropriately truncated
  209.                     * and/or expanded sequence of octets. The private
  210.                     * key was already processed (into field bx[]).
  211.                     */
  212.                    byte[] bh = bits2octets(h1);
  213.  
  214.                    /*
  215.                     * HMAC is always used with K as key.
  216.                     * Whenever K is updated, we reset the
  217.                     * current HMAC key.
  218.                     */
  219.  
  220.                    /* step b. */
  221.                    byte[] V = new byte[holen];
  222.                    for (int i = 0; i < holen; i ++) {
  223.                            V[i] = 0x01;
  224.                    }
  225.  
  226.                    /* step c. */
  227.                    byte[] K = new byte[holen];
  228.                    setHmacKey(K);
  229.  
  230.                    /* step d. */
  231.                    hmac.update(V);
  232.                    hmac.update((byte)0x00);
  233.                    hmac.update(bx);
  234.                    hmac.update(bh);
  235.                    K = hmac.doFinal();
  236.                    setHmacKey(K);
  237.  
  238.                    /* step e. */
  239.                    hmac.update(V);
  240.                    V = hmac.doFinal();
  241.  
  242.                    /* step f. */
  243.                    hmac.update(V);
  244.                    hmac.update((byte)0x01);
  245.                    hmac.update(bx);
  246.                    hmac.update(bh);
  247.                    K = hmac.doFinal();
  248.                    setHmacKey(K);
  249.  
  250.                    /* step g. */
  251.                    hmac.update(V);
  252.                    V = hmac.doFinal();
  253.  
  254.                    /* step h. */
  255.                    byte[] T = new byte[rolen];
  256.                    for (;;) {
  257.                            /*
  258.                             * We want qlen bits, but we support only
  259.                             * hash functions with an output length
  260.                             * multiple of eight; hence, we will gather
  261.                             * rlen bits, i.e. rolen octets.
  262.                             */
  263.                            int toff = 0;
  264.                            while (toff < rolen) {
  265.                                    hmac.update(V);
  266.                                    V = hmac.doFinal();
  267.                                    int cc = Math.min(V.length,
  268.                                            T.length - toff);
  269.                                    System.arraycopy(V, 0, T, toff, cc);
  270.                                    toff += cc;
  271.                            }
  272.                            BigInteger k = bits2int(T);
  273.                            if (k.signum() > 0 && k.compareTo(q) < 0) {
  274.                                    return k;
  275.                            }
  276.  
  277.                            /*
  278.                             * k is not in the proper range; update
  279.                             * K and V, and loop.
  280.                             */
  281.                            hmac.update(V);
  282.                            hmac.update((byte)0x00);
  283.                            K = hmac.doFinal();
  284.                            setHmacKey(K);
  285.                            hmac.update(V);
  286.                            V = hmac.doFinal();
  287.                    }
  288.            }
  289.  
  290.            /**
  291.             * Process one more byte of input data (message to sign).
  292.             *
  293.             * @param in   the extra input byte
  294.             */
  295.            public void update(byte in)
  296.            {
  297.                    dig.update(in);
  298.            }
  299.  
  300.            /**
  301.             * Process some extra bytes of input data (message to sign).
  302.             *
  303.             * @param in   the extra input bytes
  304.             */
  305.            public void update(byte[] in)
  306.            {
  307.                    dig.update(in, 0, in.length);
  308.            }
  309.  
  310.            /**
  311.             * Process some extra bytes of input data (message to sign).
  312.             *
  313.             * @param in    the extra input buffer
  314.             * @param off   the extra input offset
  315.             * @param len   the extra input length (in bytes)
  316.             */
  317.            public void update(byte[] in, int off, int len)
  318.            {
  319.                    dig.update(in, off, len);
  320.            }
  321.  
  322.            /**
  323.             * Produce the signature. {@link #setPrivateKey} MUST have
  324.             * been called. The signature is computed over the data
  325.             * which was input through the {@code update*()} methods.
  326.             * This engine is then reset (made ready for a new
  327.             * signature generation).
  328.             *
  329.             * @return  the signature
  330.             */
  331.            public byte[] sign()
  332.            {
  333.                    return signHash(dig.digest());
  334.            }
  335.  
  336.            /**
  337.             * <p>Produce the signature. {@link #setPrivateKey} MUST have
  338.             * been called. The signature is computed over the provided
  339.             * hash value (data is assumed to have been hashed
  340.             * externally). The data which which was input through the
  341.             * {@code update*()} methods is ignored, but kept.</p>
  342.             *
  343.             * <p>If the hash output is longer than the subgroup order
  344.             * (the length of q, in bits, denoted 'qlen'), then the
  345.             * provided value {@code h1} can be truncated, provided that
  346.             * at least qlen leading bits are preserved. In other words,
  347.             * bit values in {@code h1} beyond the first qlen bits are
  348.             * ignored.</p>
  349.             *
  350.             * @param h1   the hash value
  351.             * @return  the signature
  352.             */
  353.            public byte[] signHash(byte[] h1)
  354.            {
  355.                    if (p == null) {
  356.                            throw new IllegalStateException(
  357.                                    "no private key set");
  358.                    }
  359.                    try {
  360.                            BigInteger k = computek(h1);
  361.                            BigInteger r = g.modPow(k, p).mod(q);
  362.                            BigInteger s = k.modInverse(q).multiply(
  363.                                    bits2int(h1).add(x.multiply(r)))
  364.                                    .mod(q);
  365.  
  366.                            /*
  367.                             * Signature encoding: ASN.1 SEQUENCE of
  368.                             * two INTEGERs. The conditions on q
  369.                             * imply that the encoded version of r and
  370.                             * s is no longer than 127 bytes for each,
  371.                             * including DER tag and length.
  372.                             */
  373.                            byte[] br = r.toByteArray();
  374.                            byte[] bs = s.toByteArray();
  375.                            int ulen = br.length + bs.length + 4;
  376.                            int slen = ulen + (ulen >= 128 ? 3 : 2);
  377.                            byte[] sig = new byte[slen];
  378.                            int i = 0;
  379.                            sig[i ++] = 0x30;
  380.                            if (ulen >= 128) {
  381.                                    sig[i ++] = (byte)0x81;
  382.                                    sig[i ++] = (byte)ulen;
  383.                            } else {
  384.                                    sig[i ++] = (byte)ulen;
  385.                            }
  386.                            sig[i ++] = 0x02;
  387.                            sig[i ++] = (byte)br.length;
  388.                            System.arraycopy(br, 0, sig, i, br.length);
  389.                            i += br.length;
  390.                            sig[i ++] = 0x02;
  391.                            sig[i ++] = (byte)bs.length;
  392.                            System.arraycopy(bs, 0, sig, i, bs.length);
  393.                            return sig;
  394.  
  395.                    } catch (ArithmeticException ae) {
  396.                            throw new IllegalArgumentException(
  397.                                    "DSA error (bad key ?)", ae);
  398.                    }
  399.            }
  400.  
  401.            /**
  402.             * Reset this engine. Data input through the {@code
  403.             * update*()} methods is discarded. The current private key,
  404.             * if one was set, is kept unchanged.
  405.             */
  406.            public void reset()
  407.            {
  408.                    dig.reset();
  409.            }
  410.    }
  411.  
  412.    // ==================================================================

Paste is for source code and general debugging text.

Login or Register to edit, delete and keep track of your pastes and more.

Raw Paste

Login or Register to edit or fork this paste. It's free.