Skip to content

Instantly share code, notes, and snippets.

@TransparentLC
Last active June 25, 2021 11:50
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save TransparentLC/19a2d8b65063dc7a7beba09f150ade58 to your computer and use it in GitHub Desktop.
Save TransparentLC/19a2d8b65063dc7a7beba09f150ade58 to your computer and use it in GitHub Desktop.
2 KB 左右的 X25519 密钥交换算法实现,在 https://github.com/CryptoEsel/js-x25519 的基础上添加了 IIFE,并进行了部分修改以减小 minify 后的大小。
const X25519 = require('./x25519.min.js');
const hexToBytes = e => new Uint8Array(e.match(/[0-9a-f]{2}/gi).map(e => parseInt(e, 16)));
const bytesToHex = e => Array.from(e).map(e => e.toString(16).padStart(2, 0)).join('');
// Test vector from:
// https://datatracker.ietf.org/doc/html/rfc7748.html#section-6.1
const privateA = hexToBytes('77076d0a7318a57d3c16c17251b26645df4c2f87ebc0992ab177fba51db92c2a');
const privateB = hexToBytes('5dab087e624a8a4b79e17f8b83800ee66f3bb1292618b6fd1c2f8b27ff88e0eb');
const publicA = X25519.getPublic(privateA);
const publicB = X25519.getPublic(privateB);
console.assert(bytesToHex(publicA) === '8520f0098930a754748b7ddcb43ef75a0dbf3a0d26381af4eba4a98eaa9b4e6a');
console.assert(bytesToHex(publicB) === 'de9edb7d7b7dc1b4d35b61c2ece435373f8343c85b78674dadfc7e146f882b4f');
const sharedA = X25519.getShared(privateA, publicB);
const sharedB = X25519.getShared(privateB, publicA);
console.assert(bytesToHex(sharedA) === '4a5d9d5ba4ce2de1728e3bf480350f25e07e21c947d19e3376f09b3c1e161742');
console.assert(bytesToHex(sharedB) === '4a5d9d5ba4ce2de1728e3bf480350f25e07e21c947d19e3376f09b3c1e161742');
// Test vector from:
// https://github.com/TomCrypto/pycurve25519/blob/master/test_curve25519.py
const privateC = hexToBytes('a8abababababababababababababababababababababababababababababab6b');
const privateD = hexToBytes('c8cdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcd4d');
const publicC = X25519.getPublic(privateC);
const publicD = X25519.getPublic(privateD);
console.assert(bytesToHex(publicC) === 'e3712d851a0e5d79b831c5e34ab22b41a198171de209b8b8faca23a11c624859');
console.assert(bytesToHex(publicD) === 'b5bea823d9c9ff576091c54b7c596c0ae296884f0e150290e88455d7fba6126f');
const sharedC = X25519.getShared(privateC, publicD);
const sharedD = X25519.getShared(privateD, publicC);
console.assert(bytesToHex(sharedC) === '235101b705734aae8d4c2d9d0f1baf90bbb2a8c233d831a80d43815bb47ead10');
console.assert(bytesToHex(sharedD) === '235101b705734aae8d4c2d9d0f1baf90bbb2a8c233d831a80d43815bb47ead10');
/*
* Javascript implementation of Elliptic curve Diffie-Hellman key exchange over Curve25519
*
* Copyright (c) 2017, Bubelich Mykola
* https://bubelich.com
*
* (。◕‿‿◕。)
*
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met, 0x
*
* Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
*
* Redistributions in binary form must reproduce the above copyright notice,
* this list of conditions and the following disclaimer in the documentation
* and/or other materials provided with the distribution.
*
* Neither the name of the copyright holder nor the names of its contributors
* may be used to endorse or promote products derived from this software without
* specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
*
* Inspired by TeetNacl
*
* More information
* https://github.com/CryptoEsel/js-x25519
*
* Project
* CryptoEsel - https://cryptoesel.com
*
* References
* TweetNaCl 20140427 - http://tweetnacl.cr.yp.to/
* TweetNaCl.js v0.14.5 - https://github.com/dchest/tweetnacl-js
*
*/
(() => {
/** @type {globalThis} */
const GLOBAL = typeof globalThis !== 'undefined' ? globalThis : (global || self);
const {
Error,
Float64Array,
Uint8Array,
} = GLOBAL;
const _X25519_ZERO = new Float64Array(16)
const _X25519_ONE = new Float64Array(16)
const _X25519_NINE = new Uint8Array(32)
const _X25519_121665 = new Float64Array(16)
_X25519_NINE[0] = 0x0009
_X25519_121665[0] = 0xDB41
_X25519_121665[1] = _X25519_ONE[0] = 0x0001
/**
* Addition
*
* @param {Float64Array} result
* @param {Float64Array} augent
* @param {Float64Array} addend
* @private
*/
const _add = (result, augent, addend) => {
for (let i = 0; i < 16; i++) {
result[i] = (augent[i] + addend[i]) | 0
}
}
/**
* Subtraction
*
* @param {Float64Array} result
* @param {Float64Array} minuend
* @param {Float64Array} subtrahend
* @private
*/
const _sub = (result, minuend, subtrahend) => {
for (let i = 0; i < 16; i++) {
result[i] = (minuend[i] - subtrahend[i]) | 0
}
}
/**
*
* @param {Float64Array} values
* @private
*/
const _car25519 = (values) => {
let carry = 0
for (let i = 0; i < 16; i++) {
values[i] += 65536
carry = Math.floor(values[i] / 65536)
values[(i + 1) * (i < 15 ? 1 : 0)] += carry - 1 + 37 * (carry - 1) * (i === 15 ? 1 : 0)
values[i] -= (carry * 65536)
}
}
/**
* Copy source to destination
* Warning! length not checked!
*
* @param {Float64Array} destination
* @param {Float64Array} source
* @private
*/
const _copy = (destination, source) => {
destination.set(source.subarray(0, destination.length));
// const len = source.length
// for (let i = 0; i < len; i++) {
// destination[i] = source[i]
// }
}
/**
* Multiplication
*
* @param {Float64Array} result
* @param {Float64Array} multiplier
* @param {Float64Array} multiplicand
* @private
*/
const _mul = (result, multiplier, multiplicand) => {
let i = 0
let j = 0
let carry = new Float64Array(31)
for (i = 0; i < 16; i++) {
for (j = 0; j < 16; j++) {
carry[i + j] += multiplier[i] * multiplicand[j]
}
}
/** mul 2 x 19 **/
for (i = 0; i < 15; i++) {
carry[i] += 38 * carry[i + 16]
}
_car25519(carry)
_car25519(carry)
/** copy results **/
_copy(result, carry)
}
/**
* Compute values^2
*
* @param {Float64Array} result
* @param {Float64Array} values
* @private
*/
const _sqr = (result, values) => {
_mul(result, values, values)
}
/**
*
* @param {Float64Array} result
* @param {Float64Array} q
* @param {Number} b
* @private
*/
const _sel25519 = (result, q, b) => {
let tmp = 0
let carry = ~(b - 1)
// compute //
for (let i = 0; i < 16; i++) {
tmp = carry & (result[i] ^ q[i])
result[i] ^= tmp
q[i] ^= tmp
}
}
/**
* Pack from 8x16 -> 1x32 bytes array
*
* @param {Float64Array} result
* @param {Float64Array} values
* @private
*/
const _pack = (result, values) => {
const m = new Float64Array(16)
const tmp = new Float64Array(16)
let i = 0
let carry = 0
// copy //
_copy(tmp, values)
_car25519(tmp)
_car25519(tmp)
_car25519(tmp)
for (let j = 0; j < 2; j++) {
m[0] = tmp[0] - 0xFFED
for (i = 1; i < 15; i++) {
m[i] = tmp[i] - 0xFFFF - ((m[i - 1] >> 16) & 1)
m[i - 1] &= 0xFFFF
}
m[15] = tmp[15] - 0x7FFF - ((m[14] >> 16) & 1)
carry = (m[15] >> 16) & 1
m[14] &= 0xFFFF
_sel25519(tmp, m, 1 - carry)
}
for (i = 0; i < 16; i++) {
result[2 * i] = tmp[i] & 0xFF
result[2 * i + 1] = tmp[i] >> 8
}
}
/**
* Upack 1x32 -> 8x16 bytes arrays
*
* @param {Float64Array} result
* @param {Uint8Array} values
* @private
*/
const _unpack = (result, values) => {
for (let i = 0; i < 16; i++) {
result[i] = values[2 * i] + (values[2 * i + 1] << 8)
}
}
/**
*
* @param {Float64Array} result
* @param {Float64Array} values
* @private
*/
const _inv25519 = (result, values) => {
const carry = new Float64Array(16)
// copy values to carry //
_copy(carry, values)
// compute //
for (let i = 253; i >= 0; i--) {
_sqr(carry, carry)
if (i !== 2 && i !== 4) {
_mul(carry, carry, values)
}
}
// copy carry to results //
_copy(result, carry)
}
/**
* Core scalar multiplies for curve 25519
*
* @param {Uint8Array} multiplier; 32 bytes array
* @param {Uint8Array} multiplicand; 32 bytes array
* @private
*/
const _scalarMul = (multiplier, multiplicand) => {
const carry = new Float64Array(80)
const a = new Float64Array(_X25519_ONE)
const b = new Float64Array(_X25519_ZERO)
const c = new Float64Array(_X25519_ZERO)
const d = new Float64Array(_X25519_ONE)
const e = new Float64Array(_X25519_ZERO)
const f = new Float64Array(_X25519_ZERO)
const z = new Uint8Array(multiplier)
let r = 0
_unpack(carry, multiplicand)
// copy carry to b //
_copy(b, carry)
for (let i = 254; i >= 0; --i) {
r = (z[i >>> 3] >>> (i & 7)) & 1
_sel25519(a, b, r)
_sel25519(c, d, r)
_add(e, a, c)
_sub(a, a, c)
_add(c, b, d)
_sub(b, b, d)
_sqr(d, e)
_sqr(f, a)
_mul(a, c, a)
_mul(c, b, e)
_add(e, a, c)
_sub(a, a, c)
_sqr(b, a)
_sub(c, d, f)
_mul(a, c, _X25519_121665)
_add(a, a, d)
_mul(c, c, a)
_mul(a, d, f)
_mul(d, b, carry)
_sqr(b, e)
_sel25519(a, b, r)
_sel25519(c, d, r)
}
for (let i = 0; i < 16; i++) {
carry[i + 16] = a[i]
carry[i + 32] = c[i]
carry[i + 48] = b[i]
carry[i + 64] = d[i]
}
const x32 = carry.subarray(32)
const x16 = carry.subarray(16)
_inv25519(x32, x32)
_mul(x16, x16, x32)
const result = new Uint8Array(32)
_pack(result, x16)
return result
}
/**
* Curve 25516 clamp input seed bytes
*
* @param {Uint8Array} bytes
* @private
*/
const _clamp = (bytes) => {
bytes[0] &= 0xF8
bytes[31] = (bytes[31] & 0x7F) | 0x40
}
const X25519 = {
/**
* Generate and return public key as Uint8Array[32] array
*
* @param {Uint8Array} secretKey
* @return {Uint8Array}
*/
'getPublic': secretKey => {
if (secretKey.length !== 32) {
throw new Error('Secret key should be 32 bytes.')
}
const p = new Uint8Array(secretKey)
_clamp(p)
return _scalarMul(p, _X25519_NINE)
},
/**
* Generate shared key from secret and public key
* Length is 32 bytes for every key
*
* @param {Uint8Array} secretKey
* @param {Uint8Array} publicKey
* @return {Uint8Array}
*/
'getShared': (secretKey, publicKey) => {
if (secretKey.length !== 32 || publicKey.length !== 32) {
throw new Error('Secret key and public key should be 32 bytes.')
}
const p = new Uint8Array(secretKey)
_clamp(p)
return _scalarMul(p, publicKey)
}
};
if (typeof module !== 'undefined') {
module.exports = X25519
} else {
GLOBAL['X25519'] = X25519;
}
})();
(()=>{const e="undefined"!=typeof globalThis?globalThis:global||self,{Error:n,Float64Array:t,Uint8Array:o}=e,r=new t(16),l=new t(16),w=new o(32),f=new t(16);w[0]=9,f[0]=56129,f[1]=l[0]=1;const s=(e,n,t)=>{for(let o=0;o<16;o++)e[o]=n[o]+t[o]|0},c=(e,n,t)=>{for(let o=0;o<16;o++)e[o]=n[o]-t[o]|0},u=e=>{let n=0;for(let t=0;t<16;t++)e[t]+=65536,n=Math.floor(e[t]/65536),e[(t+1)*(t<15?1:0)]+=n-1+37*(n-1)*(15===t?1:0),e[t]-=65536*n},d=(e,n)=>{e.set(n.subarray(0,e.length))},a=(e,n,o)=>{let r=0,l=0,w=new t(31);for(r=0;r<16;r++)for(l=0;l<16;l++)w[r+l]+=n[r]*o[l];for(r=0;r<15;r++)w[r]+=38*w[r+16];u(w),u(w),d(e,w)},b=(e,n)=>{a(e,n,n)},i=(e,n,t)=>{let o=0,r=~(t-1);for(let t=0;t<16;t++)o=r&(e[t]^n[t]),e[t]^=o,n[t]^=o},y=(e,n)=>{const w=new t(80),y=new t(l),h=new t(r),g=new t(r),k=new t(l),p=new t(r),S=new t(r),m=new o(e);let A=0;((e,n)=>{for(let t=0;t<16;t++)e[t]=n[2*t]+(n[2*t+1]<<8)})(w,n),d(h,w);for(let e=254;e>=0;--e)A=m[e>>>3]>>>(7&e)&1,i(y,h,A),i(g,k,A),s(p,y,g),c(y,y,g),s(g,h,k),c(h,h,k),b(k,p),b(S,y),a(y,g,y),a(g,h,p),s(p,y,g),c(y,y,g),b(h,y),c(g,k,S),a(y,g,f),s(y,y,k),a(g,g,y),a(y,k,S),a(k,h,w),b(h,p),i(y,h,A),i(g,k,A);for(let e=0;e<16;e++)w[e+16]=y[e],w[e+32]=g[e],w[e+48]=h[e],w[e+64]=k[e];const T=w.subarray(32),E=w.subarray(16);((e,n)=>{const o=new t(16);d(o,n);for(let e=253;e>=0;e--)b(o,o),2!==e&&4!==e&&a(o,o,n);d(e,o)})(T,T),a(E,E,T);const F=new o(32);return((e,n)=>{const o=new t(16),r=new t(16);let l=0,w=0;d(r,n),u(r),u(r),u(r);for(let e=0;e<2;e++){for(o[0]=r[0]-65517,l=1;l<15;l++)o[l]=r[l]-65535-(o[l-1]>>16&1),o[l-1]&=65535;o[15]=r[15]-32767-(o[14]>>16&1),w=o[15]>>16&1,o[14]&=65535,i(r,o,1-w)}for(l=0;l<16;l++)e[2*l]=255&r[l],e[2*l+1]=r[l]>>8})(F,E),F},h=e=>{e[0]&=248,e[31]=127&e[31]|64},g={getPublic:e=>{if(32!==e.length)throw new n("Secret key should be 32 bytes.");const t=new o(e);return h(t),y(t,w)},getShared:(e,t)=>{if(32!==e.length||32!==t.length)throw new n("Secret key and public key should be 32 bytes.");const r=new o(e);return h(r),y(r,t)}};"undefined"!=typeof module?module.exports=g:e.X25519=g})()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment