RSA基础 - VA伐木累

RSA基础
•发布于 •作者 liuzy •701 次浏览 •最后一次编辑是 •来自技术

```js
/*
    Z1 = find()
    Z2 = find()
    N = Z1 * Z2
    φ(N) = (Z1 - 1) * (Z2 - 1)
    E = find(φ(N))
    D = (T * φ(N) + 1) / E
    C = Math.pow(M, E) % N
    M = Math.pow(C, D) % N
*/
// 随机取一个X以内的整数
function random(X) {
    return Math.floor(Math.random() * X + 1);
}
// 是否是质数
function isPrime(n) {
    if (n <= 3) { return n > 1; }
    if (n % 2 == 0 || n % 3 == 0) {
        return false;
    }
    for (let i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return false;
        }
    }
    return true;
}
// 随机取一个不等于X的质数
function find(X) {
    const prinmes = [];
    const idx = random(10);
    for (let n = 1;; n++) {
        if (isPrime(n)) {
            prinmes.push(n);
            if (prinmes.length == idx) {
                return n == X ? find(X) : n;
            }
        }
    }
}
// 计算X的欧拉函数
function eular(X) {
    let ret = 1;
    for (let i = 2; i * i <= X; i++)
        if (X % i == 0) {
            X /= i, ret *= i - 1;
            while (X % i == 0)
                X /= i, ret *= i;
        }
    if (X > 1)
        ret *= X - 1;
    return ret;
}

// 1.找两个不相等的质数Z1、Z2
const Z1 = find(),
    Z2 = find(Z1);
console.log(`Z1 = ${Z1}`);
console.log(`Z2 = ${Z2}`);
// 2.计算模数
const N = Z1 * Z2;
console.log(`N = ${N}`);
// 3.计算欧拉函数
const FN = eular(N)
console.log(`FN = ${FN}`);
// 4.找一个公钥
const E = function() {
    for (let i = 2; i < FN; i++) {
        if (FN % i != 0) {
            return i;
        }
    }
}()
console.log(`E = ${E}`);
// 5.计算私钥
const D = function() {
    let d;
    for (let T = 1;; T++) {
        if (T > N) {
            return NaN;
        }
        if (Number.isInteger(d = (1 + T * FN) / E) || Number.isInteger(d = (1 - T * FN) / E)) {
            return d;
        }
    }
}()
console.log(`D = ${D}`);
// 6.加密
const M = random(10);
console.log(`M = ${M}`);
const C = Math.pow(M, E) % N;
console.log(`C = Math.pow(${M}, ${E}) % ${N} = ${C}`);
// 6.解密
const M2 = Math.pow(C, D) % N;
console.log(`M = Math.pow(${C}, ${D}) % ${N} = ${M2}`);
// 结果
console.log(M == M2 ? '成功' : '失败');
// 方法是对的，但JS整型太小了，pow会科学计数，可能会失败

Z1 = 3
Z2 = 11
N = 33
FN = 20
E = 3
D = 7
M = 4
C = Math.pow(4, 3) % 33 = 31
M = Math.pow(31, 7) % 33 = 4
成功
[Finished in 0.2s]
```

0 回复

作者

liuzy

积分: 841

“ 黑眼圈圈男 ”

无人回复话题

SonarQube 9.4 + PostgreSQL

shell倒计时

日常网络巧技

使用ssh创建socks5代理服务

NodeJS集群demo

作者其他话题

SonarQube 9.4 + PostgreSQL

shell倒计时

日常网络巧技

使用ssh创建socks5代理服务

NodeJS集群demo