一兜材、ECC橢圓曲線加密算法原理
1.1典挑、橢圓曲線介紹
ECC（Elliptic Curves Cryptography狞洋，橢圓曲線加密）是一種公開密鑰算法窖维。1985年，Neal Koblitz和Victor Miller分別獨立提出了ECC妙痹≈罚基本形狀可以參考如下圖：
1.2、圖解橢圓曲線
橢圓曲線有兩個特點：
- 如果你在上方隨便畫一個點怯伊，那么下方也一定有一個對稱的點沛贪，上下方距離水平線X軸是相同的。
- 隨便在圖形上畫兩個點震贵，讓這兩個點連成線然后延長會經(jīng)過第三個點，當然除了垂直線以外水评。
根據(jù)這兩個特點我們就可以做文章了猩系。如果有A，B兩個點中燥，延長以后會經(jīng)過第三個點寇甸，而這第三個點以X軸為中心是會有一個點與其對稱，我們就把這個對稱的點先稱為C點疗涉。這里頭就像是運算過程拿霉，A和B得出C，在這里我就把運算過程稱為 “點運算”咱扣，A點B得到C绽淘，這個 “點運算”其實就是橢園曲線上的加法運算，但為了讓你們不與傳統(tǒng)加法運算弄混闹伪，這里先使用“點運算”的說法沪铭。
現(xiàn)在我們把A和C進行連線，同樣經(jīng)過了第三個點偏瓤，第三個點也有一個對稱的點杀怠，這里稱為D點，也就是A點C得到D厅克，我們再把A和D連線赔退，也經(jīng)過了第三個點，第三個點也有一個對稱的點证舟，這里稱為E點硕旗，也就是A點D得到E。
問題：已知起點是A褪储，終點是E卵渴，請問起點A經(jīng)過多少次點運算得到E？我們很難知道經(jīng)過了多少次鲤竹，這就很符合我們前面說的公鑰加密的特點：正向簡單浪读，逆向困難
我們還要考慮一種特殊情況，如果我們?nèi)∫粋€點碘橘，命名為P互订，然后畫一條直線，結(jié)果發(fā)現(xiàn)這條直線只能與橢圓曲線相交于一個點痘拆，而不是剛剛所說的一共有三個點仰禽，這種情況怎么定義運算呢？
首先解釋一下這是一條切線纺蛆，如果不記得什么是切線吐葵，那就想象這里有一個圓，而切線是垂直于經(jīng)過切點的半徑桥氏，還不明白也沒關(guān)系温峭，現(xiàn)在點P身處的這條直線相交橢圓曲線后，也有一個對稱的點字支，這里先命名為Q點凤藏， 現(xiàn)在重點來了！因為點P初始沒有和其他點連成線堕伪，不是剛剛那種開始就有兩個點來連線揖庄，因此這里就認為是P點P的運算，也就是自己點自己欠雌，所以Q就是P點P的運算結(jié)果蹄梢，也就是兩介P得到Q，我們就把點Q稱為2P富俄，因為是兩個P得出的點检号，你也可以理解為P+P=2P。
現(xiàn)在P與2P連線蛙酪，也經(jīng)過了第三個點齐苛，第三個點也有一個對稱的點，P+2P就等于3P桂塞，這個點就是3P凹蜂，那么這個過程可以一直延續(xù)下去，我們是可以得到6P這個點的阁危，6P這個點就很有靈性了玛痊，比如3P點3P，兩次的話可以得到6P狂打，也就是3P乘以2得到6P擂煞，那2P點2P，三次的話也可以得到6P趴乡，也就是2P乘以3得到6P对省，其實就是簡單的乘法問題蝗拿，只不過是橢園曲線上的，不要小看這簡單的表示方法蒿涎，等會你可能就會對著屏幕說“握草”哀托。
1.3、笛福赫爾曼(Diffie-Hellman)算法
DH 算法又稱“Diffie–Hellman 算法”劳秋，像往常的算法名字一樣仓手，這是用倆個數(shù)學牛人的名字來命名的算法，實現(xiàn)安全的密鑰交換玻淑，通訊雙方在完全沒有對方任何預(yù)先信息的條件下通過不安全信道創(chuàng)建起一個密鑰嗽冒。
如下圖示例：首先兩個要溝通的對象需要確定兩個參數(shù)，參數(shù)P和參數(shù)G补履，參數(shù)P辛慰，故名意思是一個質(zhì)數(shù)，因為P是Prime的縮寫干像，而參數(shù)G是Generator的縮寫，這里就不詳細解釋G的緣由了驰弄，因為涉及到一些數(shù)學的知識麻汰。這里我選一個簡單的質(zhì)數(shù)23，因為23乘以1等于23戚篙，沒有其它整數(shù)相乘可以得到23了五鲫，而參數(shù)G這里選擇5，這兩個參數(shù)是可以公開的岔擂，所以黑客知道也沒關(guān)系位喂。
現(xiàn)在就可以套用公式1了，5的隨機數(shù)次方除以23來求余數(shù)乱灵，這個公式也是公開的塑崖，黑客知道也沒毛病，現(xiàn)在兩邊要各自生成一個隨機數(shù)痛倚，蒜老大生成了6规婆，油大叔生成了15，各自生成的隨機數(shù)套入這個公開的公式蝉稳，也就是蒜老大進行5的6次方要除以23得到余數(shù)8抒蚜，油大叔進行5的15次方要除以23得到余數(shù)19，各自把生成的余數(shù)發(fā)送給對方耘戚。
對方收到后套用公式2嗡髓，各自收到的余數(shù)的隨機數(shù)次方除以參數(shù)P求出新的余數(shù)，對于蒜老大收津，就是用收到的19進行6次方運算再除以23得到余數(shù)2饿这，這里的數(shù)字6就是蒜大哥自己生成的隨機數(shù)浊伙，23就是前面定義好的參數(shù)P，對于油大叔來說蛹稍，就是用收到的8進行15次方運算再除以23得到余數(shù)2吧黄，這里的數(shù)字15就是油大叔自己生成的隨機數(shù)，23也是前面定義好的參數(shù)P唆姐，現(xiàn)在大家可以看到兩邊得到的余數(shù)都是一樣的拗慨，都是數(shù)字2，兩邊就可以用這個數(shù)字2來對后續(xù)的對話進行加密了奉芦，沒人知道原來他們用這個2來加密后續(xù)的對話赵抢，當然了實際上的隨機數(shù)和質(zhì)數(shù)其實并沒有這么簡單，通常都建議質(zhì)數(shù)至少要有2048比特的長度声功，就是為了防止破解烦却。
1.4、ECDH算法
ECDH是Elliptic Curve Diffie-Hellman先巴，它一種基于ECC的密鑰協(xié)商算法其爵。ECDH是笛福赫爾曼(Diffie-Hellman)算法的變種，它是一種密鑰協(xié)商協(xié)議伸蚯，定義了密鑰怎么樣在通信雙方之間生成和交換摩渺。其思路過程與笛福赫爾曼密鑰協(xié)商算法基本相同，只是在具體的協(xié)商計算中使用ECC剂邮。
如下圖示例：Alice需要生成一個私鑰小a摇幻，然后再確定橢圓曲線上的一個點：G，這個G點是公開的挥萌，是大家都可以有的G點绰姻，接著Alice需要生成公鑰大A，公鑰就利用前面說到的橢圓曲線來運算引瀑，也就是公鑰大A等于小a點G狂芋，這里的意思就是G這個點進行點運算，次數(shù)是a憨栽，也就是G點G點G點…一共a次银酗，得到了橢圓曲線上的點大A，現(xiàn)在Alice把大A和G發(fā)送給Bob徒像，也就是大A和G是公開的黍特，有同學可能就在想，別人知道大A和G锯蛀，那小a不就很容易算出來嗎灭衷？其實前面已經(jīng)說了，一定不容易旁涤，知道起點和終點翔曲，但是中間經(jīng)歷多少次是非常難知道的迫像，這就是把橢園曲線加進來的奧義。
Bob收到后瞳遍，也生成了一個私鑰小b闻妓，然后生成橢園曲線上的一個新點(大B），這個大B就是G點進行小b次運算得到的掠械，也就是G點G點G點…一共b次由缆，現(xiàn)在Bob把生成的大B發(fā)送給Alice，別人知道大B和大G兩個點也很難得到小b猾蒂，還是那句話：中間經(jīng)歷多少次很難知道【Γ現(xiàn)在Alice用私鑰小a和收到的大B進行運算得到新的密鑰，Bob用私鑰小b和收到的大A進行運算也得到了新的密鑰肚菠，這個新的密鑰就只有他們知道舔箭，也就是會話密鑰，而且這個密鑰必須是相同的蚊逢。相信你對于這個運算還有點懵层扶，你們看Alice這邊，大B其實就等于小b點G烙荷，直接從Bob那邊把等式代入就明白了镜会，而在Bob這邊，大A其實就等于小a點G奢讨，直接從Alice那邊把等式代入就明白了，這樣一看就知道密鑰是相同的焰薄，只不過小a和小b互換了位置拿诸。如果你還看不出，假設(shè)a等于3塞茅，b等于2亩码，不管是2乘以3，還是3乘以2野瘦，其實就等于6G了描沟，也就是前面提及到的運算方法，這個密鑰交換過程也就是ECDHE的原理鞭光，ECDHE就是橢園曲線和DH混合起來的密鑰交換算法吏廉。
二、openssl庫的使用
2.1惰许、openssl編譯生成靜態(tài)庫
- 首先下載openssl庫：https://github.com/krzyzanowskim/OpenSSL
- Makefile文件席覆，修改版本號，我這里使用 3.1.0 版本汹买，然后也可以選擇注釋掉"frameworks"的打包
- 20-apple.conf文件修改iOS配置參數(shù)佩伤，去除"-fembed-bitcode"聊倔。然后修改最低支持的版本'-mios-version-min=9.0‘
- build.sh文件最下方，注釋"build_macos"生巡、"build_catalyst"耙蔑，我們只打iOS環(huán)境的包。還可以選擇注釋掉"build "x86_64""孤荣，只打真機包甸陌。
- 修改homebrew的配置文件，詳情參考：https://blog.csdn.net/zhanghao143lina/article/details/128656499
- 最后執(zhí)行make指令即可垃环，打出包在Frameworks文件夾或者iphoneos文件夾中
2.2邀层、openssl生成密鑰對
可下載 Demo，相關(guān)方法存放在ZJHOpenSSLTool類中
詳見下面代碼及注釋：
/// 生成ECC曲線：256r1
+ (int)generateEccCurve:(EC_GROUP **)g_group_tem ec_key:(EC_KEY **)ec_key_tem {
// 初始化一個空算法組：這里只是用EC_GROUP_new生成一個空的group, 然后由p,a,b等參數(shù)來填充group,
// 再以這個group為基礎(chǔ)去生成曲線上的點
EC_GROUP *g_group = EC_GROUP_new(EC_GFp_mont_method());
*g_group_tem = g_group;
// 新建的密鑰結(jié)構(gòu)體（EC_KEY_new）遂庄，此時還沒有公私鑰信息
EC_KEY *ec_key = EC_KEY_new();
*ec_key_tem = ec_key;
// BN_CTX openssl中加密算法結(jié)構(gòu)體寥院，里面包含各種加密算法的函數(shù)指針
BN_CTX *g_ctx = NULL;
// 大數(shù)初始化
BIGNUM *p, *a, *b, *gx, *gy, *z;
p = BN_new();
a = BN_new();
b = BN_new();
gx = BN_new();
gy = BN_new();
z = BN_new();
// 將國密算法的參數(shù)轉(zhuǎn)為大數(shù)。這里是把定義的曲線常量轉(zhuǎn)換成大數(shù)表式涛目，這樣才能使用openssl中的接口秸谢。
BN_hex2bn(&p, _P);
BN_hex2bn(&a, _a);
BN_hex2bn(&b, _b);
BN_hex2bn(&gx, _Gx);
BN_hex2bn(&gy, _Gy);
BN_hex2bn(&z, _n); // 素數(shù)P的階
int ret = -1; // 返回碼
do {
// 先確定sm2曲線：設(shè)置素數(shù)域橢圓曲線參數(shù)
if (!EC_GROUP_set_curve_GFp(g_group, p, a, b, g_ctx)) {
ret = -2;
break;
}
// 取曲線上的三個點
EC_POINT* point_p = EC_POINT_new(g_group);
// 設(shè)置基點坐標：設(shè)置素數(shù)域橢圓曲線上點point的幾何坐標
if (!EC_POINT_set_affine_coordinates_GFp(g_group, point_p, gx, gy, g_ctx)) {
ret = -3;
break;
}
// 確定P點是否在曲線上
if (!EC_POINT_is_on_curve(g_group, point_p, g_ctx)) {
ret = -4;
break;
}
// 設(shè)置橢圓曲線的基G，完成了國密曲線：generator霹肝、order和cofactor為輸入?yún)?shù)
if(!EC_GROUP_set_generator(g_group, point_p, z, BN_value_one())) {
ret = -5;
break;
}
// 生成ECKey
if (!EC_KEY_set_group(ec_key, g_group)) {
ret = -6;
break;
}
if (point_p != NULL) {
EC_POINT_free(point_p);
}
ret = 0;
} while (NO);
return ret;
}
/// 生成公私鑰對
+ (NSArray *)generateEccKeyPair {
EC_GROUP *g_group = NULL;
EC_KEY *ec_key = NULL;
NSData *privateKeyData = nil;
NSData *publicKeyData = nil;
int ret = -1; // 返回碼
do {
// 生成曲線
ret = [self generateEccCurve:&g_group ec_key:&ec_key];
if (ret != 0) {
break;
} else {
ret = -1; // 重置一下
}
// 生成秘鑰對估蹄，在曲線上生成秘鑰對怖喻，生成橢圓曲線公私鑰
if(!EC_KEY_generate_key(ec_key)) {
ret = -7;
break;
}
unsigned char pri[32] = {0};
// EC_KEY_get0_private_key（讀取私鑰信息）
BN_bn2bin(EC_KEY_get0_private_key(ec_key), pri); // 大數(shù)轉(zhuǎn)二進制
privateKeyData = [NSData dataWithBytes:pri length:32]; // 轉(zhuǎn)換私鑰Data
// NSLog(@"privateKeyData : %@", self.privateKeyData);
// EC_KEY_get0_public_key（讀取公鑰信息）
const EC_POINT *pub_key;
unsigned char pubbuf[1024] = {0};
pub_key = EC_KEY_get0_public_key(ec_key);
/* 功能：將點的仿射坐標（以壓縮或者不壓縮形式）轉(zhuǎn)化成字符串
輸入：group剖笙，point，form【壓縮方式】肌似，len【允許的字符串大小上限】 輸出：buf【字符串】
返回：轉(zhuǎn)化得到的字符串長度 or 1【point＝∞】*/
size_t buflen = EC_POINT_point2oct(g_group, pub_key, EC_KEY_get_conv_form(ec_key), pubbuf, sizeof(pubbuf), NULL);
publicKeyData = [NSData dataWithBytes:pubbuf length:buflen]; // 轉(zhuǎn)換公鑰Data
// NSLog(@"publicKeyData : %@", self.publicKeyData);
ret = 0; // 處理成功
} while (NO);
if (g_group != NULL) { // 釋放資源
EC_GROUP_free(g_group);
}
if (ec_key != NULL) {
EC_KEY_free(ec_key);
}
if (ret < 0) {
NSLog(@"生成密鑰對失敗 code ：%d", ret);
}
if (privateKeyData && publicKeyData) { // 成功返回數(shù)據(jù)
return @[privateKeyData, publicKeyData];
}
return nil; // 失敗返回空
}
2.3讯赏、openssl的ECDH方法
詳見下面代碼及注釋：
/// ECDH 密鑰協(xié)商
+ (NSData *)computeECDHWithPublicKey:(NSString *)publicKey
privateKey:(NSString *)privateKey {
if (!publicKey || publicKey.length == 0 || !privateKey || privateKey.length == 0) {
return nil;
}
if (publicKey.length == 128) { // 可能沒有公約的首位數(shù)據(jù)垮兑，這里拼接一下04
publicKey = [NSString stringWithFormat:@"04%@",publicKey];
}
const char *public_key = publicKey.UTF8String; // 公鑰
const char *private_key = privateKey.UTF8String; // 私鑰
EC_GROUP *g_group = NULL;
EC_KEY *ec_key = NULL;
EC_POINT *pub_point = NULL; // 公鑰
BIGNUM *pri_big_num = NULL; // 私鑰
NSData *ecdhKeyData = nil; // 協(xié)商出的密鑰數(shù)據(jù)
int ret = -1; // 返回碼
do {
// 生成曲線
ret = [self generateEccCurve:&g_group ec_key:&ec_key];
if (ret != 0) {
break;
} else {
ret = -1; // 重置一下
}
// 公鑰轉(zhuǎn)換為 EC_POINT
pub_point = EC_POINT_new(g_group);
EC_POINT_hex2point(g_group, public_key, pub_point, NULL);
// 私鑰轉(zhuǎn)換為 BIGNUM 并存儲在 EC_KEY 中
if (!BN_hex2bn(&pri_big_num, private_key)) {
ret = -7;
break;
}
/* 功能：設(shè)置密鑰的點群信息 輸入：key，group
輸出：key【設(shè)置好了密鑰的點群信息】*/
if (!EC_KEY_set_group(ec_key, g_group)) {
ret = -8;
break;
}
// 設(shè)置私鑰
if (!EC_KEY_set_private_key(ec_key, pri_big_num)) {
ret = -9;
break;
}
OPENSSL_FILE;
OPENSSL_LINE;
size_t outlen = 32;
uint8_t *ecdh_text = (uint8_t *)OPENSSL_zalloc(outlen + 1);
int retCode = ECDH_compute_key(ecdh_text, outlen, pub_point, ec_key, 0);
if (retCode <= 0) {
ret = -10;
break;
}
ecdhKeyData = [NSData dataWithBytes:ecdh_text length:outlen];
OPENSSL_free(ecdh_text);
ret = 0; // 處理成功
} while (NO);
if (g_group != NULL) { // 釋放資源
EC_GROUP_free(g_group);
}
if (ec_key != NULL) {
EC_KEY_free(ec_key);
}
if (pub_point != NULL) {
EC_POINT_free(pub_point);
}
if (pri_big_num != NULL) {
BN_free(pri_big_num);
}
if (ret < 0) {
NSLog(@"密鑰協(xié)商失敗 code ：%d", ret);
}
return ecdhKeyData;
}
三漱挎、GMEllipticCurveCrypto庫的使用
可下載 Demo系枪，相關(guān)方法存放在ViewController類中
3.1、GMEllipticCurveCrypto庫簡介
GMEllipticCurveCrypto 是包含橢圓曲線數(shù)字簽名算法（ECDSA）和橢圓曲線Diffie-Hellman（ECDH）的Objective-C庫磕谅。ECDSA允許使用私鑰生成簽名私爷，并使用公鑰進行驗證。ECDH允許兩個身份使用自己的私鑰和彼此的公鑰來生成共享密鑰膊夹，然后可用于加密衬浑。該庫主要基于easy-ecc庫（https://github.com/kmackay/easy-ecc）。
- 支持：secp128r1, secp192r1, secp256r1, secp384r1
- 基于私鑰或公鑰自動檢測曲線
- 支持鍵作為原始字節(jié)或base64編碼的字符串
- BSD 2條款許可證
3.2放刨、創(chuàng)建公私鑰示例
/// GMEllipticCurveCrypto生成密鑰對
- (void)demoGMEllipticCurveCryptoGenerateEccKeyPair {
// 公鑰長度相關(guān)問題：https://stackoverflow.com/questions/69402678/swift-generate-shared-key-using-ecdh
GMEllipticCurveCrypto *crypto =
[GMEllipticCurveCrypto generateKeyPairForCurve:GMEllipticCurveSecp256r1];
NSData *pub1 = crypto.publicKey; // 32位公鑰
NSData *pub2 = [crypto decompressPublicKey:pub1]; // 還原成65位公鑰
NSLog(@"Public Key data1: %@", pub1);
NSLog(@"Public Key data2: %@", pub2);
NSLog(@"Private Key data: %@", crypto.privateKey);
NSLog(@"Public Key: %@", crypto.publicKeyBase64);
NSLog(@"Private Key: %@", crypto.privateKeyBase64);
NSLog(@"");
//
}
代碼中默認生成的密鑰長度為32位嚎卫，是壓縮后的，如果想變成65位的，需要調(diào)用 \- (NSData*)decompressPublicKey:(NSData*)publicKey;拓诸，不過該放在默認是沒有開放出來的侵佃，可以手動添加到頭文件中GMEllipticCurveCrypto.h。參考鏈接：https://stackoverflow.com/questions/69402678/swift-generate-shared-key-using-ecdh
另外需要注意的是生成的publicKeyBase64數(shù)據(jù)奠支，iOS中沒有 ASN.1 OID 的標頭數(shù)據(jù)馋辈，需要自己拼接下，具體處理可參考鏈接：https://blog.csdn.net/wei372889893/article/details/120494575
3.3倍谜、ECDH方法示例
/// GMEllipticCurveCrypto的ECDH方法
- (void)demoGMEllipticCurveCryptoECDH {
/* 公鑰：04E3517069E8D411FDD070C9141B4C22A7B29628CE9988689CB38B148F426376BBA00ECA56E3B641C9B349A6DC64BC20F916D71CBE95D28490C82F079C6BBFECFE
私鑰：C77337BB1EEDBA2B9C8C366E6EE525788156D90771CF51742D9CBFDAEEE52326
協(xié)商結(jié)果：9B9E0AAD7D0FE03BD9BC326DABB44B1C1FC547B8FD0708F6C1C15075001B7B7F
*/
NSString *pubStr = @"04E3517069E8D411FDD070C9141B4C22A7B29628CE9988689CB38B148F426376BBA00ECA56E3B641C9B349A6DC64BC20F916D71CBE95D28490C82F079C6BBFECFE";
NSString *priStr = @"C77337BB1EEDBA2B9C8C366E6EE525788156D90771CF51742D9CBFDAEEE52326";
NSData *pubData = [self dataFromHexString:pubStr];
NSData *priData = [self dataFromHexString:priStr];
// Alice performs...
GMEllipticCurveCrypto *Alice =
[GMEllipticCurveCrypto cryptoForCurve: GMEllipticCurveSecp256r1];
alice.privateKey = priData;
NSData *pubData2 = [alice compressPublicKey:pubData]; // 壓縮公鑰
NSData *shareKey = [alice sharedSecretForPublicKey:pubData2];
NSLog(@"Shared Secret: %@", shareKey);
NSString *shareKeyStr = [self hexDataToNSString:shareKey];
NSLog(@"***ZJH keyDataStr : %@", shareKeyStr);
NSLog(@"");
}
參考鏈接：
DH算法 | 迪菲-赫爾曼Diffie–Hellman 密鑰交換：https://www.bilibili.com/video/BV1sY4y1p78s/?spm_id_from=333.788&vd_source=7d8a08755bacd471929384973dc151c0
公鑰加密技術(shù)ECC橢圓曲線加密算法原理：https://www.bilibili.com/video/BV1BY411M74G/?spm_id_from=333.337.search-card.all.click&vd_source=7d8a08755bacd471929384973dc151c0
橢圓曲線加密(Elliptic Curve Cryptography)相關(guān)：http://www.reibang.com/p/a2067de6b7ac
國密算法--Openssl 實現(xiàn)國密算法(基礎(chǔ)介紹和產(chǎn)生秘鑰對)：https://blog.csdn.net/weixin_33849942/article/details/93292870
GMEllipticCurveCrypto：https://github.com/ankitthakur/GMEllipticCurveCrypto
