首页
关于
友情链接
推荐
百度一下
腾讯视频
百度一下
腾讯视频
Search
1
【笔记】用Javascript实现椭圆曲线加密算法
13 阅读
2
Hackergame 2022 个人题解
11 阅读
3
欢迎使用 Typecho
10 阅读
4
【博客折腾记录】l2d看板娘相关~
5 阅读
5
中国科学技术大学第六届信息安全大赛(HACKERGAME2019自我总结)
4 阅读
默认分类
登录
Search
标签搜索
Note
CPP
C
JavaScript
Math
CTF
Bilibili
Python
Docker
php
RSA
ECC
Crypto
Blog
Bash
FPGA
GAMES
Homework
依言 - Eyan
累计撰写
34
篇文章
累计收到
1
条评论
首页
栏目
默认分类
页面
关于
友情链接
推荐
百度一下
腾讯视频
百度一下
腾讯视频
搜索到
3
篇与
的结果
2021-07-06
【笔记】一些浏览器环境下的内置API
SHA-256const hashBrowser = val => crypto.subtle.digest('SHA-256', new TextEncoder('utf-8').encode(val)).then(h => { let hexes = [], view = new DataView(h); for (let i = 0; i < view.byteLength; i += 4) hexes.push(('00000000' + view.getUint32(i).toString(16)).slice(-8)); return hexes.join(''); }); hashBrowser(JSON.stringify({ a: 'a', b: [1, 2, 3, 4], foo: { c: 'bar' } })).then(console.log); // '04aa106279f5977f59f9067fa9712afc4aedc6f5862a8defc34552d8c7206393'AESfunction encrypt(data, keyJSON){ var data = new TextEncoder("UTF-8").encode(data); var randomsKeys = geneRandomHexStr(64); // 128 bit keys var encryptedKey = hexStringToUint8Array(randomsKeys); var aesAlgo = {name: 'aes-cbc', iv: hexStringToUint8Array("000102030405060708090a0b0c0d0e0f")}; return crypto.subtle.importKey("jwk", keyJSON, {name: "rsa-oaep", hash: {name: "sha-256"}},true, ['encrypt']) .then(function(publicKey){ return crypto.subtle.encrypt({name: "rsa-oaep"}, publicKey, encryptedKey); }).then(function(res){ encryptedKey = bytesToHexString(res) // use aes to encrypt data // import aes key return crypto.subtle.importKey('raw', hexStringToUint8Array(randomsKeys) , aesAlgo, false, ['encrypt', 'decrypt']); }).then(function(result){ // use aes to encode return crypto.subtle.encrypt(aesAlgo, result, data); }).then(function(encryptedData){ return Promise.resolve({ 'encrypted': bytesToHexString(encryptedData), 'encryptedKey': encryptedKey, }); }); //console.log(new TextDecoder("UTF-8").decode(data)); // use server public key to encrypt } function decrypt(data, keyJSON){ // use local private key to decrypt var encryptedKey = new hexStringToUint8Array(data.encryptedKey); var encryptedData = new hexStringToUint8Array(data.encrypted); var aesAlgo = {name: 'aes-cbc', iv: hexStringToUint8Array("000102030405060708090a0b0c0d0e0f")}; // decrypt key return crypto.subtle.importKey('jwk', keyJSON, {name: "rsa-oaep", hash: {name: "sha-256"}}, true, ['decrypt']).then(function(privateKey){ return crypto.subtle.decrypt({name: 'rsa-oaep'}, privateKey, encryptedKey); }).then(function(decryptedKey){ // import aes key return crypto.subtle.importKey('raw', decryptedKey, aesAlgo, false, ['encrypt', 'decrypt']); }).catch(function(){ console.error("decrypt error"); }).then(function(result){ // decode encrypted data return crypto.subtle.decrypt(aesAlgo, result, encryptedData); }).then(function(data){ return Promise.resolve(new TextDecoder("UTF-8").decode(new Uint8Array(data))); }) } function createNewUserKey(){ var algorithmKeyGen = { name: "RSA-OAEP", hash: {name: "sha-256"}, // RsaKeyGenParams modulusLength: 2048, publicExponent: new Uint8Array([0x01, 0x00, 0x01]), // Equivalent to 65537 }; var nonExtractable = false; var publicKey = ""; var privateKey = ""; var keyPairs = ""; return crypto.subtle.generateKey(algorithmKeyGen, true, ['encrypt', 'decrypt']).then(function(result) { // gene key pair keyPairs = result; return Promise.all([crypto.subtle.exportKey("jwk", keyPairs.publicKey), crypto.subtle.exportKey("jwk", keyPairs.privateKey)]); }) } function _arrayBufferToBase64( buffer ) { var binary = ''; var bytes = new Uint8Array( buffer ); var len = bytes.byteLength; for (var i = 0; i < len; i++) { binary += String.fromCharCode( bytes[ i ] ); } return window.btoa( binary ); } function hexStringToUint8Array(hexString) { if (hexString.length % 2 != 0) throw "Invalid hexString"; var arrayBuffer = new Uint8Array(hexString.length / 2); for (var i = 0; i < hexString.length; i += 2) { var byteValue = parseInt(hexString.substr(i, 2), 16); if (byteValue == NaN) throw "Invalid hexString"; arrayBuffer[i/2] = byteValue; } return arrayBuffer; } function bytesToHexString(bytes) { if (!bytes) return null; bytes = new Uint8Array(bytes); var hexBytes = []; for (var i = 0; i < bytes.length; ++i) { var byteString = bytes[i].toString(16); if (byteString.length < 2) byteString = "0" + byteString; hexBytes.push(byteString); } return hexBytes.join(""); } function geneRandomHexStr(length){ var text = ""; var possible = "0123456789abcdef"; for( var i=0; i < length; i++ ) text += possible.charAt(Math.floor(Math.random() * possible.length)); return text; } createNewUserKey().then(function(keyPairs){ encrypt("this is origin text", keyPairs[0]).then(function(res){ console.log('public', JSON.stringify(keyPairs[0])); console.log('private', JSON.stringify(keyPairs[1])); decrypt(res, keyPairs[1]).then(function(decrypted){ console.log('decrypted', decrypted); }); }); })SHA-256代码const hashBrowser = val => crypto.subtle.digest('SHA-256', new TextEncoder('utf-8').encode(val)).then(h => { let hexes = [], view = new DataView(h); for (let i = 0; i < view.byteLength; i += 4) hexes.push(('00000000' + view.getUint32(i).toString(16)).slice(-8)); return hexes.join(''); });示例hashBrowser(JSON.stringify({ a: 'a', b: [1, 2, 3, 4], foo: { c: 'bar' } })).then(console.log); // '04aa106279f5977f59f9067fa9712afc4aedc6f5862a8defc34552d8c7206393'Reference浏览器 - 使用 SHA-256 创建一个 hashReferences浏览器 - 使用 SHA-256 创建一个 hash (advanced)js 原生 aes rsa 加解密 及 CryptoJS 加解密js-sha256的完整源码(来自谷歌)
2021年07月06日
1 阅读
0 评论
0 点赞
2020-08-01
【笔记】二维码中的 Reed-Solomon 编码
如题。。因为看了某针的二维码视频,所以想试试实现自己写个,于是就有了这篇文章。这里主要研究的是二维码的纠错码。使用语言为Javascript,所有代码均可在浏览器直接运行。模二除法因为二维码的编码是在伽罗瓦域中进行的,所以需要大量用到异或和模二乘法。异或很简单,但模二乘法就很复杂了,这里先实现下模二乘法的第二部取余。模二除法的算法原理参考于模2除法(CRC校验码计算): 1 0 1 1 //商 --------------- 1 1 1 1 0 0 0 //被除数,注意首位为1 1 1 0 1 //被除数首位为1,除以除数 --------------- 0 1 0 0 0 0 //余数去除首位,作为新的被除数 0 0 0 0 //被除数首位为0,除以0 --------------- 1 0 0 0 0 //余数去除首位,作为新的被除数 1 1 0 1 //被除数首位为1,除以除数 --------------- 1 0 1 0 //余数去除首位,作为新的被除数 1 1 0 1 //被除数首位为1,除以除数 --------------- 1 1 1 //余数,此时余数位数少于除数,不能继续除了 看计算过程可以得知,模二除法就是看除的时候某一位是不是1,如果是1就用被除数和除数异或,商1,然后看下一位。我写的算法和上述有些不同,我是看在某一位的时候用被除数和除数做异或运算后被除数是否变小,如果变小则商一。这个算法其实和最简单的竖列除法差不多,都是尽可能的让被除数变小,待会的多项式除法我会用这个思路。光说可能没那么容易理解,上代码:function mod_div(a,b){ ori = b; while(a > b){ b <<= 1; } let ans = 0; while(b >= ori){ ans <<= 1; if((a ^ b) < a){ a ^= b; ans += 1; } b >>= 1; } return a; }在算法中,结果的商也被求出来了,在while结束时的ans即使商,不过由于我们只关心余数,这里就先不管它了。模二乘法接下来是模二乘法:function xor_mul(a,b){ let ans = 0; while(b > 0){ if(b&1){ ans ^= a; } b >>= 1; a <<= 1; //console.log(ans) } return ans; }算法和快速乘法差不多,这里就不多解释了。伽罗瓦域中的模二乘法(?)function mod_mul(a, b, p){ return mod_div(xor_mul(a, b),p); }有了上面的算法,就可以表示出模二乘法了。其中的p是事先设定好的数值,在视频中这个数是0b1011,也就是11 。接下来验证我们的算法,很简单,我们试着输出一张GF(2^3)的完整乘法表,然后和视频中对照一下就知道算法正确不正确了:mod_div_2 = []; var i = 0; for(i=0;i<8;++i){ mod_div_2[i] = [0,]; } table = ''; for(i=0;i<8;i++){ for(j=0;j<8;j++){ tmp = mod_mul(i, j, 11); table += tmp; table += ' '; mod_div_2[tmp][i] = j; } table += '\n'; } console.log('-----table-----'); console.log(table); console.log('-----table2-----'); console.log(mod_div_2);输出结果:-----table----- 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 0 2 4 6 3 1 7 5 0 3 6 5 7 4 1 2 0 4 3 7 6 2 5 1 0 5 1 4 2 7 3 6 0 6 7 1 5 3 2 4 0 7 5 2 1 6 4 3 -----table2----- [ [7, 0, 0, 0, 0, 0, 0, 0 ], [0, 1, 5, 6, 7, 2, 3, 4 ], [0, 2, 1, 7, 5, 4, 6, 3 ], [0, 3, 4, 1, 2, 6, 5, 7 ], [0, 4, 2, 5, 1, 3, 7, 6 ], [0, 5, 7, 3, 6, 1, 4, 2 ], [0, 6, 3, 2, 4, 7, 1, 5 ], [0, 7, 6, 4, 3, 5, 2, 1 ] ]你可能会发现这段代码和刚才我说的不太一样,事实上,这里我并不仅输出了一张乘法表,顺便还获取了一张完整除发表(实际上是刚才的逆运算,和上面的模二除法并不一样)。这在后面会用到。通过对比,我们能看到输出的这张乘法表和视频中是一样的,说明了我们算法的正确性。多项式运算接下来的运算都是把数据编码成多项式后进行的运算,所以我们需要多项式的运算。要进行多项式运算,我们首先要定义多项式。这里我直接使用数组来代表多项式。数组下标为n的元素的值代表多项式fx中x的冥为n的项的系数。例如:[1,2,3,4] 代表的就是f(x) = 4x^3 + 3x^2 + 2x + 1。多项式的加法与减法因为在前面定义过,伽罗瓦域中的加法与减法都是异或运算,所以这里的加减法都一样。function polyn_add(a, b){ // 让a的项数始终比b多。 if(a.length < b.length){ let c = a; a = b; b = c; } let ans = []; for(i=0; i<a.length; i++){ if(i < b.length){ ans.push(a[i] ^ b[i]); } else { ans.push(a[i]); } } return(ans); } var polyn_sub = polyn_add;只需要逐位进行异或运算,注意下两个多项式项数不一样的情况就行了。多项式的乘法多项式的乘法就复杂一些了,但也不算太难。两个多项式相乘,结果的最高项一定是两个多项式最高项的和,只要按照排列组合把每一项都加起来就行了。function polyn_mul(a, b){ let max_ratio = a.length + b.length - 1; console.log('max--',max_ratio) //make a longer than b if(a.length < b.length){ let c = a; a = b; b = c; } let ans = []; for(i=0; i<max_ratio; i++){ let tmp = 0; for(j=0; j<a.length; j++){ if((i-j >= 0) && (i-j < b.length)){ tmp = mod_add(tmp, mod_mul(a[j], b[i-j], 11)); } } ans.push(tmp); } return ans; }多项式的除法和乘法相比,除法就复杂多了,不过和上面的模二除法思路差不多。function polyn_div(a, b, p){ let aa = a.reverse(); let bb = b.reverse() ori_leng = bb.length; while(aa.length > bb.length){ bb.push(0); } let ans = []; while(aa.length >= ori_leng){ let tmp = aa[0]; ans.push(tmp); aa = polyn_sub(aa, bb.map(val=>mod_mul(val, mod_div_2[tmp][bb[0]], p))); aa.shift(); bb.pop(); } aa.reverse(); while(aa[0]===0&&aa.length>1){ aa.shift(); } return aa; }同样,这里的除法虽然计算出了商,但我们只关注余数,不关注商。编码有了多项式的除法后,我们就可以比较方便的计算出一段数据的纠错码了。我们只需要把原始数据后加四个零,然后除以预设的数值,所得结果即为我们要的纠错码。在视频中,预设的多项式为 `(x - 2^0)(x - 2^1)(x - 2^2)(x - 2^3)。可以通过下面的方法算出具体的值:tmpa = polyn_mul([1,1], [2,1]); tmpb = polyn_mul(tmpa, [4,1]); gx = polyn_mul(tmpb, [3,1]); //gx = (x-2^0)*(x-2^1)*(x-2^2)*(x-2^3) = [5, 7, 7, 4, 1]用下面的方法算出纠错码:function get_eccode(data){ let mx = [0,0,0,0].concat(data.reverse()); let gx = [5, 7, 7, 4, 1]; let px = polyn_div(mx, gx, 11); let eccode = data.reverse().concat(px.reverse()); return eccode;//mx } console.log(get_eccode([1,2,3,4])); //输出: [ 1, 2, 3, 4, 1, 6, 7, 4]验证数据有没有被篡改也很简单,只要用数据除以预设的多项式,若结果为0,那就是没问题。console.log(polyn_div([1,2,3,4,1,6,7,4].reverse(), [5,7,7,4,1], 11)); // 输出: [ 0 ]这样我们就得到了我们想要的编码了。数据的恢复那要是我们的数据被损坏了呢?按照视频中的思路,我们可以通过解一个四元二次方程组来获得错误的数据的位置和大小,然后就可以计算出正确的数据。但是解一个四元二次方程组对一个中学生而言显然有些过于困难了,好在数据量不大,我们可以通过遍历的方法解出答案。// 求幂算法 function mod_pow(a, b, p){ let ans = 1; for(i=0;i<b;++i){ ans = mod_mul(ans, a, p); } return ans; } // 快速多项式算法 function compute_polyn(n, a, x){ p = a[n]; for(i=n;i>0;--i){ p = a[i-1] ^ mod_mul(x, p, 11); } return p; } // 这个函数用来计算方程组的右半部分 function compute_offset(y1,y2,e1,e2,pos){ return mod_mul(y1,mod_pow(2,pos*e1,11),11) ^ mod_mul(y2,mod_pow(2,pos*e2,11),11); } // 这个函数用于在已知错误的情况下完成纠错 function correct_data(error, data){ data[error[0]] ^= error[2]; data[error[1]] ^= error[3]; return data; } function correct_error(data){ // 先算出m(2^0) ~ m(2^3)的值 m20 = compute_polyn(7, data, 1); m21 = compute_polyn(7, data, 2); m22 = compute_polyn(7, data, 4); m23 = compute_polyn(7, data, 3); ans=[];//方程组的解可能不止一个 // 遍历找解 for(y1=0;y1<8;++y1){ for(y2=0;y2<8;++y2){ for(e1=0;e1<8;++e1){ for(e2=0;e2<8;++e2){ if((compute_offset(y1,y2,e1,e2,0) === m20) && (compute_offset(y1,y2,e1,e2,1) === m21) && (compute_offset(y1,y2,e1,e2,2) === m22) && (compute_offset(y1,y2,e1,e2,3) === m23)){ ans.push([e1,e2,y1,y2]); } } } } } //输出所有可能的正确结果 return ans; } 然后我们来用视频中的例子验证下它的结果:err = correct_error([4,7,6,1,4,2,2,6]); console.log(err); err.forEach(element => { console.log(correct_data(element, [4,7,6,1,4,2,2,6])); });输出:[ [ 5, 0, 1, 7 ], [ 5, 7, 1, 7 ], [ 0, 5, 7, 1 ], [ 7, 5, 7, 1 ] ] [ 3, 7, 6, 1, 4, 3, 2, 6 ] [ 4, 7, 6, 1, 4, 3, 2, 1 ] [ 3, 7, 6, 1, 4, 3, 2, 6 ] [ 4, 7, 6, 1, 4, 3, 2, 1 ]可以注意到,代码一共帮我们找到了4个可能的解,其中第二个和第四个显然是和视频中相同的答案,只是顺序不同而已,但除了这两个答案之外还给出了另外两个答案,而且他们都是可以通过验证的,只不过现在我还不知道为什么(后记那笔记就这么多了,原理部分不多但这些代码是可以完成基本功能的。虽然还有些小bug而且还有些地方我还不会写。。现在也还正在学习这些内容。如果谁能给我一些修改建议那就感激不尽了。
2020年08月01日
4 阅读
0 评论
0 点赞
2020-07-31
【笔记】用Javascript实现椭圆曲线加密算法
之前为了一个项目所以去学了下椭圆曲线加密算法,本来是想写篇笔记细写算法的,但写了半天也没写出来什么,所以不如把自己摸索的东西用代码写出来了。之前项目用的nodejs,所以这里就用js写了。所有代码几乎全部可以直接在F12的控制台中运行。0x01 点的定义ecc中最基础计算单位自然就是一个个点了,点的定义非常简单,只要new一个对象然后赋予其点的xy坐标即可。class Point{ constructor(x,y){ this.x = BigInt(x); this.y = BigInt(y); } }由于在实际进行计算的时候涉及的数据通常都很大,所以这里把点的坐标都转换成大整数以方便后续计算。在ECC中,点只有两种运算:加法和数乘。所以这里我们先来实现这两个算法。0x02 点的加法因为点的加法的定义:画一条线穿过P和Q,则此直线必和曲线相交第三个点R。取R关于x轴的对称点-R,就是P+Q的结果。所以当我们有点 (x1, y1) (x2, y2) 的时候,就可以做出直线:$$ y-y_1=k\left(x-x_1\right)+b $$其中:$$ k=\frac{x_2-y_1}{x_2-x_1} $$有了这两个式子再和椭圆曲线:$$ y^2=x^3+ax+b $$相联立,就可以得到一个关于x的一元三次方程组,解出x3再代入1式就可以得到结果的点了。接下来是一个点和自己相加。按照定义,一个点和自己相加时画这个点的切线,得到切线的斜率后再带入13式就可以得到结果了。计算切线的斜率可以通过求导的方式计算得出:$$ F\left(x\right)=x^3+ax+b-y^2 $$$$ F_x^{'}=3x^2+a $$$$ F_y^{'}=-2y $$$$ k=-\frac{F_y^{'}}{F_x^{'}}=\frac{3x^2+a}{2y} $$联立计算,就可以得出(我不会算,我直接抄的qaq):$$ x_3=k^2-x_1-x_2 $$$$ y_3=y_1+k(x_2-x_1) $$最后再注意下,有的时候斜率k会是一个分数,这个时候我们不能直接计算小数,而要去求分母的逆元再去相乘,计算的时候忽略两个点关于x轴对称和有原点的特殊情况,就可以开始写代码了。function get_inv(x, y, p){ return x === 1n ? 1n : get_inv(y % x, y, p) * (y - y / x) % p; } function get_inverse(b,p){ return get_inv(b%p,p,p); } //这里直接给出一种逆元的求法,下面的函数是对上面的简单封装。关于逆元的内容以后再补吧。。。 //一种最大公约数算法 function get_gcd(x,y){ return y?get_gcd(y,x%y):x; } //在有限域下计算的求模 function mod(a, b) { const result = a % b; return result >= 0n ? result : b + result; } function point_add(pa, pb, a, p){ //p是预先设好的大质数,例如 secp256k1 的p为: 2n ** 256n - 2n ** 32n - 977n; //点和零点相加还得原来的点 if(pa.x === 0n && pa.y === 0n || pb.x === 0n && pb.y === 0n){ return new Point(pa.x+pb.x, pa.y+pb.y); } //对称的点相加得零点 if(pa.x === pb.x && pa.y !== pb.y){ return new Point(0, 0); } //定义分母和分子 let k,num,den; if(pa.x === pb.x && pa.y === pb.y){ //点自己和自己相加,求切线斜率 num = 3n * pa.x * pa.x + a; den = 2n * pa.y; } else { //否则就是Δy/Δx num = pa.y - pb.y; den = pa.x - pb.x; } //为了方便后面计算,先把分母和分子都换成正数。 let flag = 1; if(num * den < 0n){ flag = 0; num = num>0n?num:-num; den = den>0n?den:-den; } //求公约数 let gcd = get_gcd(num, den); num /= gcd; den /= gcd; //如果还有分母,则计算逆元 if(den !== 1n){ den = get_inverse(den, p); } k = num * den; k %= p; if(flag === 0)k = -k; //最终计算得到两点相加的结果 let x3 = mod(k*k - pa.x - pb.x, p); let y3 = mod(k * (pa.x - x3) - pa.y, p); return new Point(x3, y3); }简单的验证(节选自ECC椭圆曲线详解(有具体实例))对于椭圆曲线E23(1,1) (即y2=x3+x+1, p=23),上两点P(3,10),Q(9,7),求(2)P+Q,(3) 2P先把上面的代码都粘贴到控制台,然后:var a = 1n; var p = 23n; p1 = new Point(3n,10n); p2 = new Point(9n,7n) console.log(point_add(p1,p2,a,p)); console.log(point_add(p1,p1,a,p));得到结果:Point {x: 17n, y: 20n} Point {x: 7n, y: 12n}再和答案对比:P+Q=(17,20)2P=(7,12)可以验证我们算法的正确性。0x03 点的乘法有了点的加法后,乘法就简单多了。按照定义,nP即代表n个p相加。我们当然可以写一个循环让P加上n次,不过这样效率太低了,这里我们使用快速算法加速:function get_ng(n, g, a, p){ n = BigInt(n) let ans = new Point(0, 0); while(n > 0n){ if(n&1n){ ans = point_add(ans, g, a, p); } g = point_add(g,g,a,p); n >>= 1n; } return ans; }和整数的快速乘法原理基本相同。简单的验证var i = 0n; ans = new Point(0n, 0n); for(i=1n;i<20n;i+=1n){ ans = point_add(ans, p1, 1n, 23n); console.log(ans); console.log(get_ng(i, p1, 1n, 23n)); }输出这里就略掉了,可以看到都是一样的。0x04 椭圆曲线密钥交换算法(ECDH)ECDH跟DH的流程基本是一致的。 1.小红和小明约定使用某条椭圆曲线(包括曲线参数,有限域参数以及基点P等) 2.小红生成私钥x,计算xP作为公钥公布出去 3.小明生成私钥y,计算yP作为公钥公布出去 4.小红得知yP后,计算 s=x(yP)=xyP 5.小明得到xP后,计算 s=y(xP)=yxP 6.双方都得到了相同的密钥s(因为s是一个点,实际上会取s的横坐标值作为密钥),交换完毕。//一个生成256bit随机数的代码 function get_random_256(){ let i = 0n; let ans = 0n; for(i=0;i<64;i++){ ans += BigInt(Math.floor(Math.random()*16)); ans <<= 4n; } ans >>= 4n; return ans; } // 1.小红和小明约定使用某条椭圆曲线(包括曲线参数,有限域参数以及基点P等) // G x, y values taken from official secp256k1 document var Gx = 55066263022277343669578718895168534326250603453777594175500187360389116729240n; var Gy = 32670510020758816978083085130507043184471273380659243275938904335757337482424n; var secp_p = 2n ** 256n - 2n ** 32n - 977n; var secp_n = 2n ** 256n - 432420386565659656852420866394968145599n; secp = new Point(Gx, Gy); // 2.小红生成私钥x,计算xP作为公钥公布出去 var x = get_random_256(); var xp = get_ng(x, secp, 0n, secp_p) // 3.小明生成私钥y,计算yP作为公钥公布出去 var y = get_random_256(); var yp = get_ng(y, secp, 0n, secp_p); // 4.小红得知yP后,计算 s=x(yP)=xyP var xyp = get_ng(x, yp, 0n, secp_p); // 5.小明得到xP后,计算 s=y(xP)=yxP var yxp = get_ng(y, xp, 0n, secp_p); // 6.双方都得到了相同的密钥s(因为s是一个点,实际上会取s的横坐标值作为密钥),交换完毕。 console.log(xyp.x); console.log(yxp.x); //可以看到,二者是相同的,而且第三方没办法在只知道xP和yP的情况下计算出x或y的值。## 0x05 椭圆曲线数字签名算法ECDSA ECDSA算法要用到哈希函数,这里给出一种能直接在浏览器运行的 sha256:const hashBrowser = val => crypto.subtle.digest('SHA-256', new TextEncoder('utf-8').encode(val)).then(h => { let hexes = [], view = new DataView(h); for (let i = 0; i < view.byteLength; i += 4) hexes.push(('00000000' + view.getUint32(i).toString(16)).slice(-8)); return hexes.join(''); }); hashBrowser('hello').then(console.log); //2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824若是nodejs环境可以使用crypto库var crypto = require('crypto'); crypto.createHash('sha256').update("Hello").digest(); //<Buffer 2c f2 4d ba 5f b0 a3 0e 26 e8 3b 2a c5 b9 e2 9e 1b 16 1e 5c 1f a7 42 5e 73 04 33 62 93 8b 98 24>然后是把上述两者转换成数字的函数:function hex2num(buf){ return Bigint('0x'+buf); } function buffer2num(buf){ res = 0n for(i = 0;i < buf.length;i++){ res *= 256n; res += BigInt(buf[i]); } return res; }ESCDA的算法可以参考这篇文章:一文读懂ECDSA算法如何保护数据, 这里给出代码:var privateKey = get_random_256(); var publicKey = get_ng(privateKey, secp, 0n, secp_p); var rand = get_random_256(); function create_signature(msg, privateKey){ var rand = get_random_256(); var hash_num = buffer2num(crypto.createHash('sha256').update(msg).digest()); var tmp_point = get_ng(rand, secp, 0n, secp_p); var sig = (get_inverse(rand, secp_n)*(hash_num+privateKey*tmp_point.x))%secp_n; return [tmp_point.x, sig]; } var sig = create_signature('hello', privateKey); console.log(sig); function verify_signature(msg, sig, publicKey){ var hash_num = buffer2num(crypto.createHash('sha256').update(msg).digest()); var z = get_inverse(sig[1], secp_n); var u1 = (hash_num * z) % secp_n; var u2 = (sig[0] * z) % secp_n; var tmp_point_a = get_ng(u1, secp, 0n, secp_p); var tmp_point_b = get_ng(u2, publicKey, 0n, secp_p); var tmp_point_c = point_add(tmp_point_a, tmp_point_b, 0n, secp_p); if(tmp_point_c.x === sig[0]){ return true; } else { return false; } } console.log(verify_signature('hello', sig, publicKey));运行结果:[ 106125970590837898963543318604922501655587713131762488617508912548024413779984n, 46432126777832730161356900205711454009927346565305507216353403867728159578311n ] true算法的验证这里我决定使用nodejs中已经有的ecc库 ecccrypto 对刚才的算法进行验证:var eccrypto = require('eccrypto'); function num2buffer(num){ res = ''; table = '0123456789abcdef'; while(num > 0n){ res = table[parseInt(num&15n)]+res; num >>= 4n; } if(res.length%2==1){ res = '0'+res; } return Buffer.from(res, 'hex'); } // ecccrypto 生成的公私钥 var privateKeyA; var publicKeyA; // 之后用于计算的整数 var privateKeyB; var publicKeyB; privateKeyA = eccrypto.generatePrivate(); publicKeyA = eccrypto.getPublic(privateKeyA); privateKeyB = buffer2num(privateKeyA); publicKeyB = get_ng(privateKeyB, secp, 0n, secp_p); sig = create_signature('hello', privateKeyB); r_buffer = num2buffer(sig[0]); s_buffer = num2buffer(sig[1]); r_len = BigInt(r_buffer.length); s_len = BigInt(s_buffer.length); total_len = r_len+s_len; sig_der = Buffer.concat([ // 这里使用DER格式的签名 num2buffer(0x30n), // SEQUENCE TAG num2buffer(total_len + 4n), // SEQUENCE LEN num2buffer(0x02n), // INTEGER TAG num2buffer(r_len), // INTEGER LEN r_buffer, // INTEGER VALUE num2buffer(0x02n), // INTEGER TAG num2buffer(s_len), // INTEGER LEN s_buffer, // INTEGER VALUE ]); eccrypto.verify(publicKeyA, crypto.createHash("sha256").update('hello').digest(), sig_der).then(function() { console.log("Signature is OK"); }).catch(function() { console.log("Signature is BAD"); });最后输出:Signature is OK
2020年07月31日
13 阅读
0 评论
0 点赞