密码算法知识也很有意思——聊聊密钥交换
场景
假设 Alice 和 Bob 之间需要共享一个对称密钥，那么如何生成双方都知道的对称密码呢？
一、Diffie-Hellman 算法
（1）Alice、Bob 共同选择两个质数 P 和 G，P 是一个非常大的质数，G 可以是一个较小的数，而 G 是和 P 相关的数，我们称之为生成元。
生成元概念：
对于生成元的概念可以理解为：G 的 n(1<n<13)次方 modP 的值没有重复的数字，则 G 为 P 的生成元。
举个例子说明：
选取质数 P=17，我们来画出对应的乘方表，横向表示 n 的值，竖向为 0-16，表示 P 个数字，表格中的数字表示 G 的 n 次方 modP 的值。
可以看到没有重复的 3、5、6、7、10、11、12、14，这几个数可以成为 17 的生成元。
（2）Alice 生成一个随机数 A 是一个 1 到 P-2 的整数，这个数字只有 Alice 知道的秘密数字
（3）Bob 生成一个随机数 B 是一个 1 到 P-2 的整数，这个数也只有 Bob 知道的秘密数字
（4）Alice 将 G 的 A 次方 Mod P 这个数字发送给 Bob
（5）Bob 将 G 的 B 次方 Mod P 这个数字发送给 Alice
（6）Alice 用 Bob 发送过来的数计算 A 次方 Mod P
（7）Bob 用 Alice 发送过来的数计算 B 次方 Mod P
（8）Alice 和 Bob 计算得出的数即是对称密钥
具体实践
（1）Alice 和 Bob 选取 P=17，生成元选择 G=6
（2）Alice 生成随机数，在 1 到 15 之间，选择 9，这个只有 Alice 知道
（3）Bob 生成随机数，选择 5，这个只有 Bob 知道
（4）Alice 计算 6 的 9 次方 mod17，值为 11，发送给 Bob
（5）Bob 计算 6 的 5 次方 mod17，值为 7，发送给 Alice
（6）Alice 计算 7 的 9 次方 mod17，算出 10
（7）Bob 计算 11 的 5 次方 mod17，值为 10
两者算出的数据是一样的，10 即可做为对称密钥进行加密
程序实现
import java.math.BigInteger;
import java.security.SecureRandom;
public class Main {
private static final BigInteger G = new BigInteger("6");
private static final BigInteger P = new BigInteger("17");
public static void main(String[] args) throws Exception{
// BigInteger aliceRandomKey = creatRandomKey();
BigInteger aliceRandomKey= new BigInteger("9");
System.out.println("aliceRandomkey:" + aliceRandomKey);
BigInteger aliceSharedKey = G.modPow(aliceRandomKey,P);
System.out.println("aliceSharekey:" + aliceSharedKey);
System.out.println("-----------");
// BigInteger bobRandomKey = creatRandomKey();
BigInteger bobRandomKey = new BigInteger("5");
System.out.println("bobRandomkey:" + bobRandomKey);
BigInteger bobSharedKey = G.modPow(bobRandomKey,P);
System.out.println("bobSharekey:" + bobSharedKey);
System.out.println("-----------");
BigInteger bobSecretKEey = aliceSharedKey.modPow(bobRandomKey,P);
System.out.println("bobSecretkey:" + bobSecretKEey);
BigInteger aliceSecretKey = bobSharedKey.modPow(aliceRandomKey,P);
System.out.println("aliceSecretkey:" + aliceSecretKey);
System.out.println("-----------");
}
private static BigInteger creatRandomKey() {
SecureRandom random = new SecureRandom();
return new BigInteger(128,random);
}
}
运行结果如下：
aliceRandomkey:9
aliceSharekey:11
-----------
bobRandomkey:5
bobSharekey:7
-----------
bobSecretkey:10
aliceSecretkey:10
-----------
继续生成大素数来计算，增加生成大素数的函数：
import java.math.BigInteger;
import java.security.SecureRandom;
public class Main {
// private static final BigInteger G = new BigInteger("6");
private static final BigInteger[] P_G = GeneratePrime();
// private static final BigInteger P = new BigInteger("17");
public static void main(String[] args) throws Exception{
BigInteger P = P_G[0];
// BigInteger G = BigInteger.valueOf(2);
BigInteger G = P_G[1];
System.out.println("前期协商：");
System.out.println("大素数P:n"+P);
System.out.println("生成元G:n"+G);
System.out.println("-----------");
BigInteger aliceRandomKey = creatRandomKey();
// BigInteger aliceRandomKey= new BigInteger("9");
System.out.println("alice的私钥自己保留:n" + aliceRandomKey);
BigInteger aliceSharedKey = G.modPow(aliceRandomKey,P);
System.out.println("alice的公钥给bob:n" + aliceSharedKey);
System.out.println("-----------");
BigInteger bobRandomKey = creatRandomKey();
// BigInteger bobRandomKey = new BigInteger("5");
System.out.println("bob的私钥自己保留:n" + bobRandomKey);
BigInteger bobSharedKey = G.modPow(bobRandomKey,P);
System.out.println("bob的公钥，给alice:n" + bobSharedKey);
System.out.println("-----------");
BigInteger bobSecretKEey = aliceSharedKey.modPow(bobRandomKey,P);
System.out.println("bob的对称密钥:n" + bobSecretKEey.toString(16).toUpperCase());
BigInteger aliceSecretKey = bobSharedKey.modPow(aliceRandomKey,P);
System.out.println("alice的对称密钥:n" + aliceSecretKey.toString(16).toUpperCase());
System.out.println("-----------");
System.out.println("生成对称密钥是否一致:n aliceSecretKey.equals(bobSecretKEey)="+aliceSecretKey.equals(bobSecretKEey));
}
private static BigInteger creatRandomKey() {
SecureRandom random = new SecureRandom();
return new BigInteger(128,random);
}
private static BigInteger[] GeneratePrime(){
SecureRandom random = new SecureRandom();
BigInteger p,g,x;
while(true){
BigInteger randomInteger = new BigInteger(128,random);
p = randomInteger.multiply(BigInteger.valueOf(2)).add(BigInteger.valueOf(1));
if(p.isProbablePrime(20)) break;
}
while(true){
//不知道啥意思
g=BigInteger.probablePrime(2,random);
x=g.multiply(g).mod(p);
if(!x.equals(BigInteger.valueOf(1))) {
break;
}
}
BigInteger[] p_g = new BigInteger[2];
p_g[0]=p;
p_g[1]=g;
return p_g;
}
}
生成结果如下：
前期协商：
大素数P:
465957916549228929162646876312952214881
生成元G:
2
-----------
alice的私钥自己保留:
293532663256373215794426282975466914381
alice的公钥给bob:
221049576364988598058830660805593563106
-----------
bob的私钥自己保留:
327420628190480823876128718062565586609
bob的公钥，给alice:
52968291471295762863405312408709330158
-----------
bob的对称密钥:
1042D19452B042D2123279D1F47B0E097
alice的对称密钥:
1042D19452B042D2123279D1F47B0E097
-----------
生成对称密钥是否一致:
aliceSecretKey.equals(bobSecretKEey)=true
可以看到生成的对称密钥是一致的。
PS：由于大数生成元的计算相当耗资源，所以上述代码并未采用真实生成元的代码来生成，对于生成元的代码可以参考：
import java.math.BigInteger;
public class LargeNumberPrimitiveRoot {
public static BigInteger power(BigInteger base, BigInteger exponent, BigInteger mod) {
BigInteger result = BigInteger.ONE;
while (exponent.compareTo(BigInteger.ZERO) > 0) {
if (exponent.and(BigInteger.ONE).compareTo(BigInteger.ONE) == 0) {
result = result.multiply(base).mod(mod);
}
base = base.multiply(base).mod(mod);
exponent = exponent.shiftRight(1);
}
return result;
}
// 检查是否为原根
public static boolean isPrimitiveRoot(BigInteger number, BigInteger mod) {
BigInteger phi = mod.subtract(BigInteger.ONE); // 计算模的欧拉函数值
for (BigInteger i = BigInteger.ONE; i.compareTo(phi) < 0; i = i.add(BigInteger.ONE)) {
if (power(number, i, mod).compareTo(BigInteger.ONE) == 0) {
return false;
}
}
return true;
}
// 找出给定数字的原根
public static BigInteger findPrimitiveRoot(BigInteger number) {
BigInteger mod = number.subtract(BigInteger.ONE); // 假设 number 是素数
for (BigInteger i = BigInteger.valueOf(2); i.compareTo(number) < 0; i = i.add(BigInteger.ONE)) {
if (isPrimitiveRoot(i, number)) {
return i;
}
}
return BigInteger.ZERO; // 未找到原根
}
public static void main(String[] args) {
BigInteger inputNumber = new BigInteger("17");
BigInteger primitiveRoot = findPrimitiveRoot(inputNumber);
if (primitiveRoot.compareTo(BigInteger.ZERO) != 0) {
System.out.println("数字 " + inputNumber + " 的原根是：" + primitiveRoot);
} else {
System.out.println("未找到数字 " + inputNumber + " 的原根。");
}
}
}
例如上述计算 17 的生成元，输出：
数字 17 的原根是：3经测试数字到了 17000000，计算原根就相当慢了
中间人攻击
这个算法需要在安全通道中进行传输，若是一开始 P 和 G 都被 Eve 知道后，它同样可以选择随机数来分别和 Alice 和 Bob 来做密钥交换，这样 Eve 同时掌握了 Alice 的对称密钥和 Bob 的对称密钥，这样数据将被中间人截获后同样可以解密出来。
解决方案一是可以私下约定好 P 和 G 的值，也可以采用 HTTPS 来传递 P 和 G。
二、采用公私钥方式
这个原理很简单，Alice 要给 Bob 传递信息，Bob 生成公私钥，把公钥给到 Alice，Alice 生成随机数，用公钥加密后给到 Bob，Bob 用私钥解密出随机数，拿到 Alice 的随机数 A，Bob 生成随机数 B，用 A 加密 B，传递给 Alice，Alice 用自己的随机数 A 解密出 B 来，这样 Alice 和 Bob 都拿到了随机数 A 和 B，用 A 和 B 组合即可生成对称密钥
程序实现
import com.tencent.kona.crypto.KonaCryptoProvider;
import javax.crypto.Cipher;
import javax.crypto.spec.IvParameterSpec;
import javax.crypto.spec.SecretKeySpec;
import java.math.BigInteger;
import java.nio.charset.StandardCharsets;
import java.security.*;
import java.util.Base64;
public class DDHExample {
private static final Provider KONA_CRYPTO_PROVIDER = new KonaCryptoProvider();
private static final byte[] SALT = {
(byte) 0x00, (byte) 0x01, (byte) 0x02, (byte) 0x03,
(byte) 0x04, (byte) 0x05, (byte) 0x06, (byte) 0x07,
(byte) 0x08, (byte) 0x09, (byte) 0x10, (byte) 0x11,
(byte) 0x12, (byte) 0x13, (byte) 0x14, (byte) 0x15,
};
//Bob生成公私钥
private static KeyPair generateKeyMaterial(String algorithm, int keySize) throws Exception {
Security.addProvider(KONA_CRYPTO_PROVIDER);
KeyPairGenerator keyGen = KeyPairGenerator.getInstance(algorithm);
SecureRandom secureRandom = new SecureRandom();
keyGen.initialize(keySize, secureRandom);
return keyGen.generateKeyPair();
}
//公钥加密函数
private static String encryptSM2(String plainText, PublicKey PublicKey) throws Exception {
Cipher cipher = Cipher.getInstance("SM2");
cipher.init(Cipher.ENCRYPT_MODE, PublicKey);
byte[] encryptedBytes = cipher.doFinal(plainText.getBytes(StandardCharsets.UTF_8));
return Base64.getEncoder().encodeToString(encryptedBytes);
}
//公钥解密函数
private static String sm2Decrypt(String encryptedText, PrivateKey PrivateKey) throws Exception {
Cipher cipher = Cipher.getInstance("SM2");
cipher.init(Cipher.DECRYPT_MODE, PrivateKey);
byte[] encryptedBytes = Base64.getDecoder().decode(encryptedText.getBytes(StandardCharsets.UTF_8));
byte[] decryptedBytes = cipher.doFinal(encryptedBytes);
return new String(decryptedBytes, StandardCharsets.UTF_8);
}
//对称加密函数
private static String encryptSM4CBC(String plainText, byte[] keyBytes, byte[] ivBytes) throws Exception {
// SecretKey secretKey = new SM4KeySpec(key);
Key key = new SecretKeySpec(keyBytes, "SM4");
IvParameterSpec ivSpec = new IvParameterSpec(ivBytes);
Cipher cipher = Cipher.getInstance("SM4/CBC/PKCS7Padding", KONA_CRYPTO_PROVIDER);
cipher.init(Cipher.ENCRYPT_MODE, key, ivSpec);
byte[] encryptedBytes = cipher.doFinal(plainText.getBytes(StandardCharsets.UTF_8));
return Base64.getEncoder().encodeToString(encryptedBytes);
}
// 对称解密函数
public static String decryptSM4CBC(String encryptedText, byte[] keyBytes, byte[] ivBytes) throws Exception {
Key key = new SecretKeySpec(keyBytes, "SM4");
Cipher cipher = Cipher.getInstance("SM4/CBC/PKCS7Padding", KONA_CRYPTO_PROVIDER);
IvParameterSpec ivSpec = new IvParameterSpec(ivBytes);
cipher.init(Cipher.DECRYPT_MODE, key, ivSpec);
byte[] encryptedBytes = Base64.getDecoder().decode(encryptedText.getBytes(StandardCharsets.UTF_8));
byte[] decryptedBytes = cipher.doFinal(encryptedBytes);
return new String(decryptedBytes, StandardCharsets.UTF_8);
}
public static void main(String[] args) throws Exception {
KeyPair BobKeyPair = generateKeyMaterial("SM2", 256);//使用SM2生成密钥对
//Alice 使用Bob的公钥进行随机数加密
SecureRandom secureRandom = new SecureRandom();
BigInteger AliceRandom = new BigInteger(128,secureRandom);
System.out.println("Step1:Alice生成随机数n"+AliceRandom);
String ALiceEncryptedText = encryptSM2(AliceRandom.toString(), BobKeyPair.getPublic());
System.out.println("---------------------------");
System.out.println("Step2:Alice使用Bob的公钥进行加密,把加密串发送给Bobn"+ALiceEncryptedText);
System.out.println("---------------------------");
System.out.println("Step3:Bob拿到加密字符串n"+ALiceEncryptedText);
//Bob使用私钥进行解密，同时生成随机数
BigInteger BobRandom = new BigInteger(128,secureRandom);
System.out.println("---------------------------");
System.out.println("Step4:Bob生成随机数n"+BobRandom);
String AliceDecryptedText = sm2Decrypt(ALiceEncryptedText,
BobKeyPair.getPrivate());
System.out.println("---------------------------");
System.out.println("Step4:Bob用自己的私钥解密出Alice的随机数n"+AliceDecryptedText);
String bshareKey = Base64.getEncoder().encodeToString(
(AliceDecryptedText + BobRandom).
getBytes(StandardCharsets.UTF_8));
System.out.println("---------------------------");
System.out.println("Step5:Bob将两个随机数组合到一起拿到的对称密钥");
System.out.println(bshareKey);
// Bob用Alice的随机数加密自己的随机数
String BobEncryptedText = encryptSM4CBC(BobRandom.toString(),
AliceRandom.toByteArray(), SALT);
System.out.println("---------------------------");
System.out.println("Step6:Bob使用ALice的随机数加密自己的随机数n"+BobEncryptedText);
//Alice 用自己的随机数解密Bob的随机数
String BobDecryptedText = decryptSM4CBC(BobEncryptedText,
AliceRandom.toByteArray(),SALT);
System.out.println("---------------------------");
System.out.println("Step7:ALice使用自己的随机数解密出Bob的随机数n"+BobDecryptedText);
String ashareKey = Base64.getEncoder().encodeToString(
(AliceRandom + BobDecryptedText).
getBytes(StandardCharsets.UTF_8));
System.out.println("---------------------------");
System.out.println("Step8:Alice将两个随机数组合到一起拿到的对称密钥");
System.out.println(ashareKey);
System.out.println("---------------------------");
System.out.println("Step9:ALice和Bob的对称密钥一致，交换密钥成功");
}
}
程序输出：
Step1:Alice生成随机数
286262369159248328129045993523603419367
---------------------------
Step2:Alice使用Bob的公钥进行加密,把加密串发送给Bob
MIGPAiBYAttHr031fXP37HuNZmCPpbczMH5aTVHUORO9Cg/8AAIgT3YVAl2tOtxodg0FATw4ondf6ry7uh4CZeS+fOpglr8EIEMhXIpJCc1/7w6maglZCgjLnrbtwbUAP0kGqKrclJtABCdztYxTiHsVv20OA0wiyezOYHtwU9lDiJCbEakmTec6MLOHClqCiuY=
---------------------------
Step3:Bob拿到加密字符串
MIGPAiBYAttHr031fXP37HuNZmCPpbczMH5aTVHUORO9Cg/8AAIgT3YVAl2tOtxodg0FATw4ondf6ry7uh4CZeS+fOpglr8EIEMhXIpJCc1/7w6maglZCgjLnrbtwbUAP0kGqKrclJtABCdztYxTiHsVv20OA0wiyezOYHtwU9lDiJCbEakmTec6MLOHClqCiuY=
---------------------------
Step4:Bob生成随机数
279988318518417779955952602950070381887
---------------------------
Step4:Bob用自己的私钥解密出Alice的随机数
286262369159248328129045993523603419367
---------------------------
Step5:Bob将两个随机数组合到一起拿到的对称密钥
Mjg2MjYyMzY5MTU5MjQ4MzI4MTI5MDQ1OTkzNTIzNjAzNDE5MzY3Mjc5OTg4MzE4NTE4NDE3Nzc5OTU1OTUyNjAyOTUwMDcwMzgxODg3
---------------------------
Step6:Bob使用ALice的随机数加密自己的随机数
3MPWgTiVTx6dJa69k14TbOUc++rZmiIuuYbyXH8FuDtaJm+9F4C5ndeaZXI2Ldzr
---------------------------
Step7:ALice使用自己的随机数解密出Bob的随机数
279988318518417779955952602950070381887
---------------------------
Step8:Alice将两个随机数组合到一起拿到的对称密钥
Mjg2MjYyMzY5MTU5MjQ4MzI4MTI5MDQ1OTkzNTIzNjAzNDE5MzY3Mjc5OTg4MzE4NTE4NDE3Nzc5OTU1OTUyNjAyOTUwMDcwMzgxODg3
---------------------------
Step9:ALice和Bob的对称密钥一致，交换密钥成功原文始发于微信公众号（YY的黑板报）：密码算法知识也很有意思——聊聊密钥交换
免责声明:文章中涉及的程序(方法)可能带有攻击性，仅供安全研究与教学之用，读者将其信息做其他用途，由读者承担全部法律及连带责任，本站不承担任何法律及连带责任；如有问题可邮件联系(建议使用企业邮箱或有效邮箱,避免邮件被拦截，联系方式见首页)，望知悉。
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论