I'm trying to use SubtleCrypto (interface of the Web Crypto API) to generate an RSA private key. But in the validation step, the manually calculated public exponent differs from JWK.e in 50% of cases. The same behaviour on Chrome, Edge and Firefox.
šWho can explain where the bug is hiding?šµš¼
Most important code parts (full code at the end):
// 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);
For now, if "wrong" e comes then I'm re-running generation.
Full code:
After run, call generateRSAPrivateKeyObject() and you will see some logs in console
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;
Your script uses the Euler totient function (p - 1, q - 1). Most modern implementations apply the Carmichael totient function lcm(p - 1, q - 1) instead.
If your script uses the Carmichael totient function instead of the Euler totient function, the public exponents always match.
The following script is based on your script, but allows the selection of the totient function via a menu. In the case of the Carmichael totient function the exponents always match, in the case of the Euler totient function they do not (proving that the WebCrypto API does indeed apply the Carmichael totient function):
async function generateRSAPrivateKeyObject(trigger) {
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 {
let retries = 20;
let count = 1;
console.clear();
console.log(`Totient: ${document.getElementById('EulerId').checked ? 'Euler' : 'Carmichael'}`);
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)
};
})
}
function gcd(a, b) {
return b == 0 ? a : gcd(b, a % b);
}
function trunc(data) {
return data.length > 16 ? (data.substr(0, 16) + '...') : data
}
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, document.getElementById('EulerId').checked ? phi : lambda);
const isExpValid = jwk.e === pubExp;
const isModulusValid = jwk.n === jwk.p * jwk.q;
if (!(isExpValid && isModulusValid)) {
console.log(`Test ${count} failed:`);
console.log('\tpublic exp', isExpValid, trunc(jwk.e.toString()), trunc(pubExp.toString()));
console.log('\tn == p * q', 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) {
count++;
return generateJWK().then(jwkValidator);
} else if (retries == 0) {
console.log(`${count} tests successfully performed with:`);
console.log('\tpublic exp', isExpValid, trunc(jwk.e.toString()), trunc(pubExp.toString()));
console.log('\tn == p * q', isModulusValid);
} 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)
}
}
async function startTest(trigger) {
await generateRSAPrivateKeyObject(trigger);
}<p>Select the totient function applied:</p>
<table><tr>
<td width = '100px' align='center'><input type="radio" id="EulerId" name="totient" value="Euler">
<label for="EulerId">Euler</label></td>
<td width = '100px' align='center'><input type="radio" id="CarmichaelId" name="totient" value="Carmichael" checked >
<label for="CarmichaelId">Carmichael</label></td>
<td width = '100px' align='center'><input type="button" id="startId" name="start" value="Start test" onclick="startTest();"/></td>
</tr></table>