Hi everyone, I’m developer FTD. Today we will introduce DSA algorithm in asymmetric encryption algorithm.

Introduction to DSA algorithm

DigitalSignature Algorithm (DSA) is a variant of Schnorr and ElGamal Signature algorithms. It is adopted by NIST as the Standard of DigitalSignature Standard (DSS).

DSA is a more advanced authentication method. It is a public-key algorithm that cannot be used to encrypt data. It is generally used for digital signature and authentication. DSA includes not only public and private keys, but also digital signatures. The private key encryption generates the digital signature, and the public key validates the data and signature. In DSA digital signature and authentication, the sender uses his private key to sign the file or message, and the receiver uses the sender’s public key to verify the authenticity of the signature, including the integrity of the data and the identity of the data sender. If the data and signature do not match, the authentication is considered failed! The function of digital signature is to verify that data is not modified during transmission.

DSA digital signature can be understood as the upgrade of one-way encryption. It verifies not only data integrity but also the identity of the sender. Moreover, it uses asymmetric keys to ensure the security of the key, so it is more secure than message digest algorithm.

DSA is an algorithm that differs from RSA in that it cannot be used for encryption or decryption, nor can it be used for key exchange, but only for signing. It is much faster than RSA.

DSA algorithm signature process


  1. The message digest algorithm is used to encrypt data to generate a message digest.
  2. The sender encrypts the message digest with its own DSA private key to form a digital signature.
  3. The original packet and the encrypted digital signature are sent to the receiver over the Internet.
  4. The receiver decrypts the digital signature with the sender’s public key and generates the same information digest for the received data using message digest algorithm.
  5. Compare and verify the decrypted information summary with the received data summary generated by re-encryption at the receiver. If the two are consistent, it indicates that the information is not damaged or tampered in the transmission process. Otherwise, it indicates that the information has lost security and confidentiality.

DSA algorithm principle

DSA is based on the integer finite field discrete logarithm problem, and its security is similar to RSA. An important feature of DSA is that the two prime numbers are exposed, so that when you use someone else’s p and Q, even if you don’t know the private keys, you can tell if they were randomly generated or tampered with.

DSA algorithm parameter definition
  • P: a prime module whose value is 2^(L-1) < P < 2^L, where L is a multiple of 64 and 512≤ L ≤ 1024
  • The prime factor of q :(p-1), whose value is 2^159 < q < 2^160, i.e., q has a length of 160 bits.
  • G: g = powm(h,(p-1)/q,p). H is any integer satisfying 1 < h < p-1, thus powM (h,(p-1)/q,p) > 1
  • X: private key. X is a randomly or pseudo-randomly generated integer whose value is 0 < x < q.
  • Y: public key. y = powm(g,x,p)

“Note:“

  1. The integers p, q, and g can be exposed or shared only by a specific set of users.
  2. The private key X and the public key Y are called a key pair (X, Y). The private key can only be held by the signer, while the public key can be published publicly. A key pair can be used continuously for a period of time.
DSA signature process:
  1. Generate a random number k whose value is 0 < k < q
  2. Calculate r = powm(g,k,p) mod q such that r > 0
  3. Calculate s = (k^(-1)(SHA(M) + x * r)) mod q such that s > 0

“Note:“

  1. K ^(-1) is the inverse of the integer k with respect to a module, not the reciprocal of k. K must be regenerated at each signature, so that the same K is not used for other signature operations!

    • Inverse element: a and b that satisfy (a * b) mod m = 1 are the inverse elements of each other with respect to the module m, expressed as a = b^(-1) or b = a^(-1). If (2 * 5) mod 3 = 1, then 2 and 5 are each other’s inverses of module 3.

  2. SHA(M) : indicates the hash value of M, where M is the plaintext to be signed. SHA is a one-way hash function. In DSS, SHA1 algorithm is selected, and SHA(M) is a 160-bits long numeric string, which meets the irreversibility and collision resistance.

  3. The final signature is the certificate pair (R, S), which is sent to the verifier along with M.

  4. Even though the probability that r and s are 0 is fairly small, if either of them is 0, k must be regenerated and r and S recalculated.

DSA verification signature process:

We use (r’, S ‘, M’) to denote the result of a signature obtained by the verifier in some way. The reason for this is that you cannot guarantee that the result of your signature is the original signature generated by the sender. On the contrary, it may have been tampered with or even dropped. For the sake of simplicity, (r, s, M) is substituted for (r’, s’, M’).

In order to verify whether the signature of (r, S, M) is actually signed by the sender, the verifier needs to have (g, P, q, y), and the verification process is as follows:

  1. Calculate w = s to the minus 1 mod q
  2. Calculate u1 = (SHA(M) * w) mod q
  3. Calculate u2 = (r * w) mod q
  4. Calculate v = (((g^ U1) * (y^ U2)) mod p) mod q = ((g^ U1 mod p) * (y^ U2 mod p) mod p) mod q = (powM (g, u1, p) * powm(y, u2, p) mod p) mod q
  5. If v is equal to r, the authentication passes; otherwise, the authentication fails

“Note:“

  1. Verification: The signature (r, S) is valid, that is, (r, S, M) is the real signature result of the sender, the authenticity can be highly trusted, and M has not been tampered, so it is valid information.
  2. Verification failure: The signature (r, S) is invalid, that is, the signature (r, S, M) is unreliable, or M is tampered with, or the signature of M is forged, or the signature of M is wrong, and M is invalid.

DSA algorithm implementation

DSA key generation:

public static Map<String, Object> initKey(String seed) throws Exception {

    KeyPairGenerator keygen = KeyPairGenerator.getInstance(KEY_ALGORITHM);

    // Initialize the random generator

    SecureRandom secureRandom = new SecureRandom();

    secureRandom.setSeed(seed.getBytes());

    keygen.initialize(1024, secureRandom);



    KeyPair keys = keygen.genKeyPair();



    PublicKey publicKey = keys.getPublic();

    PrivateKey privateKey = keys.getPrivate();



    Map<String, Object> map = new HashMap<String, Object>(2);

    map.put(PUBLIC_KEY, publicKey);

    map.put(PRIVATE_KEY, privateKey);



    return map;

}

Copy the code

Generate a digital signature for information with a private key:

public static String sign(byte[] data, String privateKey) throws Exception {

    // Decrypt the base64-encoded private key

    byte[] keyBytes = Base64.decodeBase64(privateKey);



    Construct the PKCS8EncodedKeySpec object

    PKCS8EncodedKeySpec pkcs8KeySpec = new PKCS8EncodedKeySpec(keyBytes);



    // KEY_ALGORITHM Specifies the encryption algorithm

    KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);



    // Get the private key object

    PrivateKey priKey = keyFactory.generatePrivate(pkcs8KeySpec);



    // Use the private key to generate a digital signature for the information

    Signature signature = Signature.getInstance(SIGNATURE_ALGORITHM);

    signature.initSign(priKey);

    signature.update(data);



    return Base64.encodeBase64String(signature.sign());

}

Copy the code

Verify digital signature:

public static boolean verify(byte[] data, String publicKey, String sign)

        throws Exception {



    // Decrypts the base64-encoded public key

    byte[] keyBytes = Base64.decodeBase64(publicKey);



    Construct the X509EncodedKeySpec object

    X509EncodedKeySpec keySpec = new X509EncodedKeySpec(keyBytes);



    // KEY_ALGORITHM Specifies the encryption algorithm

    KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);



    // Get the male key object

    PublicKey pubKey = keyFactory.generatePublic(keySpec);



    Signature signature = Signature.getInstance(SIGNATURE_ALGORITHM);

    signature.initVerify(pubKey);

    signature.update(data);



    // Verify that the signature is normal

    return signature.verify(Base64.decodeBase64(sign));

}

Copy the code

❝

For the full code visit:

Github.com/ForTheDevel…

❞

conclusion

DSA algorithm should be the leader in the field of digital signature. Asymmetric key greatly enhances the security of the algorithm and has been widely used in the field of digital signature.

“Writing is not easy, if you like this article, please like and forward, your attention is our motivation to continue to move forward“

About the author

  • GitHub:github.com/ForTheDevel…

  • The Denver nuggets: juejin. Cn/user / 120472…

  • CSDN:blog.csdn.net/ForTheDevel…

  • Segmentfault:segmentfault.com/u/for_the_d…

Contact the author

  • Wechat id: “ForTheDeveloper”

  • Official account: “ForTheDevelopers”