公共指数与基于exportKey('jwk')中的JWK (d, p, q)计算的不同

问题描述 投票：0回答：1

我正在尝试使用 SubtleCrypto（Web Crypto API 的接口）生成 RSA 私钥。 但在验证步骤中，手动计算的公共指数在 50% 的情况下与 JWK.e 不同。 Chrome、Edge 和 Firefox 上的行为相同。

🔎谁能解释一下bug藏在哪里？🕵🏼

最重要的代码部分（完整代码在最后）：

// 1. Key
crypto.subtle.generateKey(
  {
    name: "RSA-OAEP",
    modulusLength: 1024,
    publicExponent: new Uint8Array([0x01, 0x00, 0x01]), // 65537 in little-endian
    hash: "SHA-256",
  }
  true,
 ["encrypt", "decrypt"]
)

// 2. Export
crypto.subtle.exportKey("jwk", keyPair.privateKey)

// 3. Converting JWK (d, p, q, e, n)  to BigInt
// 4. Validation RSA params

const pubExp = modInverse(jwk.d, (jwk.p - 1n) * (jwk.q - 1n));
const isExpValid =  jwk.e === pubExp;
const isModulusValid =  jwk.n === jwk.p * jwk.q;

console.log('public exp', isExpValid, jwk.e, pubExp);
console.log('n == p * q', isModulusValid);

目前，如果“错误”的 e 出现，那么我将重新运行生成。

完整代码：

运行后，调用generateRSAPrivateKeyObject()，您将在控制台中看到一些日志

function generateRSAPrivateKeyObject() {

const r16 = 16;

const onError = {
    modulus: BigInt(0).toString(r16),
    privateExponent: BigInt(0).toString(r16),
    p: BigInt(0).toString(r16),
    q: BigInt(0).toString(r16),
};

try {

    function modInverse(a, m) {
        let m0 = m;
        let x0 = 0n;
        let x1 = 1n;

        while (a > 1n) {
            const q = a / m;
            let t = m;

            m = a % m;
            a = t;

            t = x0;
            x0 = x1 - q * x0;
            x1 = t;
        }

        if (x1 < 0n) {
            x1 += m0;
        }

        return x1;
    }

    function b64ToBn(b64) {
        const bin = atob(b64);
        const hex = [];

        bin.split('').forEach(function (ch) {
            let h = ch.charCodeAt(0).toString(r16);
            if (h.length % 2) { h = '0' + h; }
            hex.push(h);
        });

        return BigInt('0x' + hex.join(''));
    }

    function urlBase64ToBase64(str) {
        const r = str % 4;
        if (2 === r) {
            str += '==';
        } else if (3 === r) {
            str += '=';
        }
        return str.replace(/-/g, '+').replace(/_/g, '/');
    }

    function base64urlDecode(base64url) {
        return b64ToBn(urlBase64ToBase64(base64url));
    }

    function generateJWK() {
        return crypto.subtle.generateKey(
            {
                name: "RSA-OAEP",
                modulusLength: 1024,
                publicExponent: new Uint8Array([0x01, 0x00, 0x01]), // 65537 in little-endian
                hash: "SHA-256",
            },
            true,
            ["encrypt", "decrypt"]
        )
            .then((keyPair) => {
                return crypto.subtle.exportKey("jwk", keyPair.privateKey);
            })
            .then((privateKeyJWK) => {
                return {
                    n: base64urlDecode(privateKeyJWK.n),
                    p: base64urlDecode(privateKeyJWK.p),
                    q: base64urlDecode(privateKeyJWK.q),
                    d: base64urlDecode(privateKeyJWK.d),
                    e: base64urlDecode(privateKeyJWK.e)
                };
            })
    }

    let retries = 20;

    function jwkValidator(jwk) {

        const pubExp = modInverse(jwk.d, (jwk.p - 1n) * (jwk.q - 1n));
        const isExpValid =  jwk.e === pubExp;
        const isModulusValid =  jwk.n === jwk.p * jwk.q;

        console.log('public exp', isExpValid, jwk.e, pubExp);
        console.log('n == p * q', isModulusValid);

        if (isExpValid && isModulusValid) {
            return {
                modulus: jwk.n.toString(r16),
                p: jwk.p.toString(r16),
                q: jwk.q.toString(r16),
                privateExponent: jwk.d.toString(r16)
            };
        } else {

            retries--;

            if (retries > 0) {
                console.log('Retrying generation...');
                return generateJWK().then(jwkValidator);
            } else {
                return onError;
            }
        }
    }

    return generateJWK().then(jwkValidator).catch((e) => {
        console.error("Error generating RSA private key:", e);
        return onError;
    });

} catch (e) {
    console.error("Error generating RSA private key:", e);
    return Promise.resolve(onError)
}

}

window.generateRSAPrivateKeyObject = generateRSAPrivateKeyObject;
javascript rsa webcrypto-api
1个回答
0
投票

大多数现代实现（显然像 WebCrypto API）使用 Carmichael 而不是 Euler totient 函数。
如果应用 Carmichael 的 totient 函数 

lcm(p - 1, q - 1)
而不是 Euler 的 totient 函数 
(p - 1, q - 1)
，脚本中的公共指数会匹配，请参阅 here 了解有关两个函数之间差异的更多详细信息。

以下脚本基于您的脚本，但使用 Carmichael 函数，最多运行测试 10 次，如果计算的指数与 WebCrypto 指数不同则终止。
每次执行时测试都会运行到最后，证明指数始终匹配。

(async () => {

function generateRSAPrivateKeyObject() {

const r16 = 16;

const onError = {
    modulus: BigInt(0).toString(r16),
    privateExponent: BigInt(0).toString(r16),
    p: BigInt(0).toString(r16),
    q: BigInt(0).toString(r16),
};

try {

    function modInverse(a, m) {
        let m0 = m;
        let x0 = 0n;
        let x1 = 1n;

        while (a > 1n) {
            const q = a / m;
            let t = m;

            m = a % m;
            a = t;

            t = x0;
            x0 = x1 - q * x0;
            x1 = t;
        }

        if (x1 < 0n) {
            x1 += m0;
        }

        return x1;
    }

    function b64ToBn(b64) {
        const bin = atob(b64);
        const hex = [];

        bin.split('').forEach(function (ch) {
            let h = ch.charCodeAt(0).toString(r16);
            if (h.length % 2) { h = '0' + h; }
            hex.push(h);
        });

        return BigInt('0x' + hex.join(''));
    }

    function urlBase64ToBase64(str) {
        const r = str % 4;
        if (2 === r) {
            str += '==';
        } else if (3 === r) {
            str += '=';
        }
        return str.replace(/-/g, '+').replace(/_/g, '/');
    }

    function base64urlDecode(base64url) {
        return b64ToBn(urlBase64ToBase64(base64url));
    }

    function generateJWK() {
        return crypto.subtle.generateKey(
            {
                name: "RSA-OAEP",
                modulusLength: 1024,
                publicExponent: new Uint8Array([0x01, 0x00, 0x01]), // 65537 in little-endian
                hash: "SHA-256",
            },
            true,
            ["encrypt", "decrypt"]
        )
            .then((keyPair) => {
                return crypto.subtle.exportKey("jwk", keyPair.privateKey);
            })
            .then((privateKeyJWK) => {
                return {
                    n: base64urlDecode(privateKeyJWK.n),
                    p: base64urlDecode(privateKeyJWK.p),
                    q: base64urlDecode(privateKeyJWK.q),
                    d: base64urlDecode(privateKeyJWK.d),
                    e: base64urlDecode(privateKeyJWK.e)
                };
            })
    }

    let retries = 10;

    function gcd(a, b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    function jwkValidator(jwk) {

        const lambda = (jwk.p - 1n) * (jwk.q - 1n) / gcd((jwk.p - 1n), (jwk.q - 1n)); // Carmichael, lcm(a, b) = a * b / gcd(a, b), see https://stackoverflow.com/a/48462473/9014097 
        const phi = (jwk.p - 1n) * (jwk.q - 1n); // Euler

        const pubExp = modInverse(jwk.d, lambda);  // match with WebCrypto result
        //const pubExp = modInverse(jwk.d, phi);   // doesn't match with WebCrypto result
        const isExpValid =  jwk.e === pubExp;
        const isModulusValid =  jwk.n === jwk.p * jwk.q;

        console.log('public exp', isExpValid, jwk.e, pubExp);
        console.log('n == p * q', isModulusValid);

        if (!(isExpValid && isModulusValid)) {
            return {
                modulus: jwk.n.toString(r16),
                p: jwk.p.toString(r16),
                q: jwk.q.toString(r16),
                privateExponent: jwk.d.toString(r16)
            };
        } else {

            retries--;

            if (retries > 0) {
                console.log('\nRetrying generation...');
                return generateJWK().then(jwkValidator);
            } else {
                return onError;
            }
        }
    }

    return generateJWK().then(jwkValidator).catch((e) => {
        console.error("Error generating RSA private key:", e);
        return onError;
    });

} catch (e) {
    console.error("Error generating RSA private key:", e);
    return Promise.resolve(onError)
}

}

generateRSAPrivateKeyObject = generateRSAPrivateKeyObject();

})();

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.