micro-rsa-dsa-dh

micro-rsa-dsa-dh

Minimal implementation of older cryptography algorithms: RSA, DSA, DH.

• 🔻 Tree-shakeable: unused code is excluded from your builds
• 🔑 RSA (Rivest-Shamir-Adleman) public-key cryptosystem, with OAEP, PSS, PKCS1
• ✍️ DSA (Digital Signature Algorithm) signatures
• 🤝 DH (Diffie-Hellman) key exchange
• 📦 ElGamal encryption
• 5️⃣ Primality tests
• 🪶 16KB (gzipped)

[!WARNING] Like in all JS implementations, keep in mind timing leaks

Usage

npm install micro-rsa-dsa-dh

deno add jsr:@paulmillr/micro-rsa-dsa-dh

We support all major platforms and runtimes.

A standalone file micro-rsa-dsa-dh.js is also available.

• All imports
• RSA
  • OAEP
  • PSS
  • PKCS1
• DSA
• DH
• ElGamal
• Primality tests
• Security

All imports

import { DH, DHGroups } from 'micro-rsa-dsa-dh/dh.js';
import { DSA } from 'micro-rsa-dsa-dh/dsa.js';
import { ElGamal, genElGamalParams } from 'micro-rsa-dsa-dh/elgamal.js';
import {
  millerRabin,
  jacobi,
  lucas,
  bailliePSW,
  isProbablePrime,
  isProbablePrimeRSA,
  isProbablySafePrime,
} from 'micro-rsa-dsa-dh/primality.js';
import {
  IFCPrimes,
  keygen,
  mgf1,
  OAEP,
  PSS,
  PKCS1_KEM,
  PKCS1_SHA1,
  PKCS1_SHA224,
  PKCS1_SHA256,
  PKCS1_SHA384,
  PKCS1_SHA512,
  PKCS1_SHA512_224,
  PKCS1_SHA512_256,
  PKCS1_SHA3_224,
  PKCS1_SHA3_256,
  PKCS1_SHA3_384,
  PKCS1_SHA3_512,
} from 'micro-rsa-dsa-dh/rsa.js';

RSA

RSA is most common example of integer factorization cryptography (IFC).

KEM version of RSA (encrypt/decrypt) is slow and usually used to exchange AES/ChaCha keys.

OAEP

OAEP is Optimal Asymmetric Encryption Padding.

Use if you need KEM (encrypt/decrypt).

import { deepStrictEqual } from 'node:assert';
import * as rsa from 'micro-rsa-dsa-dh/rsa.js';
import { sha256 } from '@noble/hashes/sha2.js';
const alice = rsa.keygen(2048);
const oaep = rsa.OAEP(sha256, rsa.mgf1(sha256));
const msg = new Uint8Array([1, 2, 3]);
const encrypted = oaep.encrypt(alice.publicKey, msg);
deepStrictEqual(oaep.decrypt(alice.privateKey, encrypted), msg);

PSS

Use if you need signatures (sign/verify).

import { deepStrictEqual } from 'node:assert';
import * as rsa from 'micro-rsa-dsa-dh/rsa.js';
import { sha256 } from '@noble/hashes/sha2.js';
const alice = rsa.keygen(2048);
const pss = rsa.PSS(sha256, rsa.mgf1(sha256));
const msg = new Uint8Array([1, 2, 3]);
const sig = pss.sign(alice.privateKey, msg);
deepStrictEqual(pss.verify(alice.publicKey, msg, sig), true);

PKCS1

This is old standard, OAEP/PSS is better.

Signatures:

import { deepStrictEqual } from 'node:assert';
import * as rsa from 'micro-rsa-dsa-dh/rsa.js';
const alice = rsa.keygen(2048);
const pkcs = rsa.PKCS1_SHA256;
const msg = new Uint8Array([1, 2, 3]);
const sig = pkcs.sign(alice.privateKey, msg);
deepStrictEqual(pkcs.verify(alice.publicKey, msg, sig), true);

KEM (vulnerable [1], [2] ):

import { deepStrictEqual } from 'node:assert';
import * as rsa from 'micro-rsa-dsa-dh/rsa.js';
const alice = rsa.keygen(2048);
const pkcs = rsa.PKCS1_KEM;
const msg = new Uint8Array([1, 2, 3]);
const encrypted = pkcs.encrypt(alice.publicKey, msg);
deepStrictEqual(pkcs.decrypt(alice.privateKey, encrypted), msg);

DH

Same as ECDH, seems safe if pre-defined groups are used. Cons:

• Long keys
• Harder to protect from timing attacks
• Using custom non-standard groups can make algorithm weak

import { deepStrictEqual } from 'node:assert';
import { DH, DHGroups } from 'micro-rsa-dsa-dh/dh.js';
const dh = DH('modp18');
const alicePriv = dh.randomPrivateKey();
const alicePub = dh.getPublicKey(alicePriv);

const bobPriv = dh.randomPrivateKey();
const bobPub = dh.getPublicKey(bobPriv);

deepStrictEqual(dh.getSharedSecret(alicePriv, bobPub), dh.getSharedSecret(bobPriv, alicePub));

DSA

[!NOTE] DSA was deprecated in FIPS186-5.

Same as ECDSA, but with big numbers. Cons:

• Deprecated
• No pre-defined groups: need to generate and send params
• Long keys
• Harder to protect from timing attacks

import { deepStrictEqual } from 'node:assert';
import * as dsa from 'micro-rsa-dsa-dh/dsa.js';
import { sha256 } from '@noble/hashes/sha2.js';
// 1. Params
// Carol generates random params
const carolParams = dsa.genDSAParams(2048, 256, sha256, 1);
// Instead of sending primes to Alice and Bob (which can be insecure), she sends seed
// This ensures that params are not constructed primes, but generated randomly:
// Alice and Bob can use these params without trusting Carol.
const seed = carolParams.domainParameterSeed;

const aliceParams = dsa.genDSAParams(2048, 256, sha256, 1, seed);
deepStrictEqual(aliceParams, carolParams); // Same params as Carol!

const bobParams = dsa.genDSAParams(2048, 256, sha256, 1, seed);
deepStrictEqual(aliceParams, bobParams); // Now Bob has same params too!

// 2. Keys
const aliceDSA = dsa.DSA(aliceParams);
const alicePrivKey = aliceDSA.randomPrivateKey();
const alicePubKey = aliceDSA.getPublicKey(alicePrivKey); // Alice generates public key and sends to Bob
const msg = new Uint8Array([1, 2, 3, 4, 5]);
const sig = aliceDSA.sign(alicePrivKey, msg); // Alice signs message

const bobDSA = dsa.DSA(bobParams);
// Now Bob can verify that message was sent by Alice (and not Carol for example).
deepStrictEqual(bobDSA.verify(alicePubKey, msg, sig), true);

ElGamal

Mostly for educational purpose: almost nobody uses it.

import { deepStrictEqual } from 'node:assert';
import { ElGamal, genElGamalParams } from 'micro-rsa-dsa-dh/elgamal.js';
// NOTE: this is super slow! 512: 1s, 1024: 20s, 2048: 1046s
const params = genElGamalParams(512);
const elgamal = ElGamal(params);

const alicePriv = elgamal.randomPrivateKey();
const alicePub = elgamal.getPublicKey(alicePriv);
// Encryption
const msg = 12345n; // bigint, because there is not spec for padding/hashing
const cipherText = elgamal.encrypt(alicePub, msg); // Somebody encrypts message using Alice public key
deepStrictEqual(elgamal.decrypt(alicePriv, cipherText), msg); // Alice can decrypt message using private key
// Sign
const sig = elgamal.sign(alicePriv, msg); // Alice sings message using private key
deepStrictEqual(elgamal.verify(alicePub, msg, sig), true); // Other parties can verify it using Alice public key

Primality tests

A bunch of primality tests.

import { deepStrictEqual } from 'node:assert';
import * as primality from 'micro-rsa-dsa-dh/primality.js';
deepStrictEqual(primality.millerRabin(7n, 10), true);
deepStrictEqual(primality.lucas(7n), true);
deepStrictEqual(primality.bailliePSW(7n), true);
deepStrictEqual(primality.isProbablePrime(7n, 30), true); // Tests 30 random bases
deepStrictEqual(primality.isProbablySafePrime(7n, 10), true);

	Reliable	Deterministic	Note
millerRabin	No	No	Non-deterministic Miller-Rabin test over random bases (multiple iterations).
lucas	No	Yes	Deterministic Lucas test. Generally slower than the Miller-Rabin test but can be more reliable for certain numbers.
bailliePSW	Yes	Yes	Deterministic test which consists of Miller-Rabin with base 2 and Lucas test. Suitable for critical applications where the highest reliability is required.
isProbablePrime	Yes	No	Non-deterministic test from FIPS186-5. This is an enhanced version of the Baillie-PSW test, incorporating multiple rounds of the Miller-Rabin test with random bases
isProbablySafePrime	Yes	No	Non-deterministic safe prime test. Slow. Tests if a number is a probable safe prime. A safe prime is a prime number of the form p = 2q + 1, where both p and q are prime.

• Reliable: no false positives are known
• Deterministic: it does not rely on randomness

Security

All algorithms use JS bigints, which are not constant-time. When timing attacks could be mounted, they will reveal sensitive information.

That generally means:

• Document, mail, messaging encryption, like PGP, is probably OK. It's hard for an attacker to measure timings: they don't know how long it took to create a msg
• Public APIs are NOT safe. Consider something like "send us document and we will auto-sign it". These cases can leak private keys

For comparison, bigint-based elliptic curve implementations will leak much less info. That's because they operate over much smaller numbers: think 2^256, instead of 2^2048.

Links

• RFC 3447 - old RSA
• RFC 8017 - OAEP/PSS/PKCS1
• RFC 8702 - RSA-PSS + Shake
• FIPS 186-5 - Prime generation
• FIPS 186-4 - DSA
• RFC 2631 - DH
• RFC 3526 - DH groups
• RFC 6979 - DSA

License

MIT (c) Paul Miller (https://paulmillr.com), see LICENSE file.