Please, help me to understand, why the snippet below fails to decrypt the message sometimes (it successes best 5 out 6 times) when ran multiple times.
It generates an 1024-bit rsa keys pair, then encrypts "Hello World!!" in most naive way possible, doubles ciphertext, decrypts doubled ciphertext, and finally divides the result to get original plaintext. At the step of decryption it could be clearly seen (logging doubled_decr) when it is going wildly off.
As the given plaintext is small, it should recover from doubling well. bigint-mod-arith package, used for modular exponentiation here, is maintained and have some tests (though really big numbers only in performance section) in it, was used for a number of times, and doesn't seem to be a cause.
import {generateKeyPairSync, privateDecrypt, publicEncrypt, constants} from "node:crypto";
import * as modAr from "bigint-mod-arith";
// "Generate a 1024 bit RSA key pair." https://cryptopals.com/sets/6/challenges/46
const keys = generateKeyPairSync("rsa", {modulusLength: 1024});
let jwk_export = keys.privateKey.export({format: "jwk"});
let pt_test = Buffer.from("Hello World!!");
let ct_test = naiveEncrypt(pt_test, keys.publicKey);
let doubled = bigintFromBuf(ct_test)
* modAr.modPow(2, bigintFromParam(jwk_export.e), bigintFromParam(jwk_export.n));
let doubled_decr = naiveDecrypt(Buffer.from(doubled.toString(16), "hex"), keys.privateKey);
console.debug(pt_test, "plaintext buffer");
console.debug(doubled_decr, "homomorphically doubled buffer (after decryption)");
console.debug(
"_Decrypted doubled buffer divided back by 2 and converted to text_:",
Buffer.from((bigintFromBuf(doubled_decr) / 2n).toString(16), "hex").toString()
)
function bigintFromParam(str) {return bigintFromBuf(Buffer.from(str, "base64url"))}
function bigintFromBuf(buf) {return BigInt("0x" + buf.toString("hex"))}
function naiveEncrypt(message, publicKey) {
const keyParameters = publicKey.export({format: "jwk"});
// console.debug(bigintFromParam(keyParameters.e));
// console.debug(bigintFromParam(keyParameters.n));
return Buffer.from(modAr.modPow(
bigintFromBuf(message),
bigintFromParam(keyParameters.e),
bigintFromParam(keyParameters.n)
).toString(16), "hex");
}
function naiveDecrypt(message, privateKey) {
const keyParameters = privateKey.export({format: "jwk"});
// console.debug(bigintFromParam(keyParameters.d));
console.assert(
bigintFromParam(keyParameters.e) == modAr.modInv(
bigintFromParam(keyParameters.d),
(bigintFromParam(keyParameters.q) - 1n) * (bigintFromParam(keyParameters.p) - 1n)
)
);
return Buffer.from(modAr.modPow(
bigintFromBuf(message),
bigintFromParam(keyParameters.d),
bigintFromParam(keyParameters.n)
).toString(16), "hex");
}
There are two problems, one fundamental and one 'just coding':
you need to divide the 'doubled' plaintext by 2 in the modular ring Zn not the plain integers Z. In general to divide in Zn we modular-multiply by the modular inverse -- a over b = a*modInv(b,n)%n -- but for the particular case of 2 we can simplify to just a/2 or (a+n)/2
when you take bigint.toString(16) the result is variable length depending on the value of the bigint. Since RSA cryptograms are for practical purposes uniform random numbers in [2,n-1], with a 1024-bit key most of the time the result is 128 digits, but about 1/16 of the time is it 127 digits, 1/256 of the time it is 126 digits, etc. If the number of digits is odd, doing Buffer.from(hex,'hex') throws away the last digit and produces a value that is very wrong for your purpose.
In standard RSA we conventionally represent all cryptograms and signatures as a byte string of fixed length equal to the length needed to represent n -- for a 1024-bit key always 128 bytes even if that includes leading zeros. For your hacky scheme, it is sufficient if we have an even number of digits -- 126 is okay, but not 127.
I simplified your code some to make it easier for me to test -- in particular I compute the bigint versions of n,e,d once and reuse them -- but only really changed bigintToBuf and halve= per above, to get the following which works for me (in node>=16 so 'crypto' supports jwk export):
const modAr=require('bigint-mod-arith'); // actually I use the IIFE for reasons but that makes no difference
const jwk=require('crypto').generateKeyPairSync('rsa',{modulusLength:1024}).privateKey.export({format:'jwk'});
const n=bigintFromParam(jwk.n), e=bigintFromParam(jwk.e), d=bigintFromParam(jwk.d);
function bigintFromParam(str){ return bigintFromBuf(Buffer.from(str,'base64url')); }
function bigintFromBuf(buf){ return BigInt('0x'+buf.toString('hex')); }
function bigintToBuf(x){ let t=x.toString(16); return Buffer.from(t.length%2?'0'+t:t,'hex');}
let plain=Buffer.from('Hello world!');
let encr=bigintToBuf(modAr.modPow(bigintFromBuf(plain),e,n));
let double=bigintToBuf(bigintFromBuf(encr)*modAr.modPow(2n,e,n))
// should actually take mod n there to get an in-range ciphertext,
// but the modPow(,,n) in the next step = decrypt fixes that for us
let decr=bigintToBuf(modAr.modPow(bigintFromBuf(double),d,n));
let temp=bigintFromBuf(decr), halve=bigintToBuf(temp%2n? (temp+n)/2n: temp/2n);
console.log(halve.toString());
PS: real RSA implementations, including the 'crypto' module, don't use modPow(,d,n) for decryption, they use the "Chinese Remainder" parameters in the private key to do a more efficient computation instead. See wikipedia for a good explanation.
PPS: just for the record, 1024-bit RSA -- even with decent padding -- has been considered marginal for security since 2013 at latest and mostly prohibited, although there is not yet a reported break in the open community. However, that is offtopic for SO, and your exercise clearly isn't about security.