Cryptographer & number theorist: MQL recipes

Recipes

RSA key pair, encryption and decryption by hand
Diffie-Hellman key exchange on a safe prime
Birthday paradox and hash collisions
Signing a document hash and the avalanche effect
Password entropy, brute-force time and bcrypt
Two-time pad: breaking a reused one-time key
Period and balance of an 8-bit LFSR keystream
Key space and unicity distance of classical ciphers
Timing side channel of a password check
Hill cipher with a 2 x 2 key matrix

executed on MentDB

RSA key pair, encryption and decryption by hand

Build a toy RSA key from two 13-digit primes: modulus, Euler totient, Carmichael lambda, private exponent, then encrypt and decrypt a message and show that such a small modulus is factored at once.

Pipeline

01 · primesTwo primes p, qarith next_prime→02 · totientphi(n) and lambda = lcm(p-1, q-1)arith phi→03 · private keyd = e^-1 mod lambdaarith invmod→04 · encryptc = m^e mod n, m = c^d mod narith powmod→05 · attackFactor n by Pollard rhoarith factors

Script

admin

#1. Two primes of 13 digits;
-> "[p]" (arith next_prime 1000000000000);
-> "[q]" (arith next_prime 2718281828459);
#2. Modulus, Euler totient and Carmichael lambda, exact big integers;
-> "[n]" (arith frac_mul [p] [q]);
-> "[phi]" (arith phi [n]);
-> "[lambda]" (arith lcm (arith frac_sub [p] 1) (arith frac_sub [q] 1));
#3. Public exponent 65537 and private exponent d = e^-1 mod lambda;
-> "[e]" 65537;
-> "[d]" (arith invmod [e] [lambda]);
#4. Encrypt then decrypt a message;
-> "[m]" 4242424242424242;
-> "[c]" (arith powmod [m] [e] [n]);
concat "p = " [p] ", q = " [q] ", n = " [n] ", phi = " [phi] ", gcd e,phi = " (arith gcd [e] [phi]) ", d = " [d] ", c = " [c] ", decrypted = " (arith powmod [c] [d] [n]) "; a 25-digit n falls to Pollard rho: " (arith factors [n])

Result

mentdb

p = 1000000000039, q = 2718281828489, n = 2718281828595012991311071, phi = 2718281828591294709482544, gcd e,phi = 1, d = 804592673633645580693305, c = 613712918085463783433425, decrypted = 4242424242424242; a 25-digit n falls to Pollard rho: [1000000000039,2718281828489]

Go further

Speed up the decryption with the Chinese remainder theorem: arith irem of d by p-1 and q-1, arith invmod q p
Check that 65537 is prime with arith is_prime and try another public exponent with arith gcd

executed on MentDB

Diffie-Hellman key exchange on a safe prime

Check that p = 1000000000000007243 is a safe prime (p = 2q + 1, q prime), prove that 2 generates the whole group, run a Diffie-Hellman exchange and estimate the cost of a baby-step giant-step attack.

Pipeline

01 · safe primeq = (p-1)/2 and primalityarith iquo→02 · ordersDivisors of p-1arith divisors→03 · generator2^q mod p = p-1arith powmod→04 · exchangeShared key g^abarith powmod→05 · securitysqrt(p) stepsarith isqrt

Script

admin

#1. A safe prime p = 2q + 1 of 19 digits;
-> "[p]" 1000000000000007243;
-> "[q]" (arith iquo (arith frac_sub [p] 1) 2);
#2. Orders of the elements divide p - 1: only 1, 2, q, 2q;
-> "[div]" (arith divisors (arith frac_sub [p] 1));
#3. p = 3 mod 8 so 2 is a non residue: g^q = -1 and 2 generates the group;
-> "[g]" 2;
-> "[gen]" (concat "p mod 8 = " (arith irem [p] 8) ", g^2 mod p = " (arith powmod [g] 2 [p]) ", g^q mod p = " (arith powmod [g] [q] [p]));
#4. Alice and Bob exchange g^a and g^b;
-> "[A]" (arith powmod [g] 123456789012345 [p]);
-> "[B]" (arith powmod [g] 987654321098765 [p]);
-> "[KA]" (arith powmod [B] 123456789012345 [p]);
-> "[KB]" (arith powmod [A] 987654321098765 [p]);
concat "p prime: " (arith is_prime [p]) ", q prime: " (arith is_prime [q]) ", 2q+1 = " (arith frac_add (arith frac_mul 2 [q]) 1) ", divisors of p-1: " [div] "; " [gen] "; shared keys " [KA] " / " [KB] "; baby-step giant-step needs about " (arith isqrt [p]) " steps"

Result

mentdb

p prime: 1, q prime: 1, 2q+1 = 1000000000000007243, divisors of p-1: [1,2,500000000000003621,1000000000000007242]; p mod 8 = 3, g^2 mod p = 4, g^q mod p = 1000000000000007242; shared keys 690405244812504770 / 690405244812504770; baby-step giant-step needs about 1000000000 steps

Go further

Use a 2048-bit safe prime: arith next_prime and arith is_prime work on any size
Find the discrete logarithm of a small example by brute force with a for loop and arith powmod

executed on MentDB

Birthday paradox and hash collisions

Compute exactly the probability that 23 people share a birthday (365!/342! over 365^23 with 30 digits), compare with lgamma, a sum of logarithms and the usual approximation, then size the birthday attack on a 64-bit hash.

Pipeline

01 · arrangements365!/342! exactlyarith npr→02 · exact ratioDivision with 30 digitsbigdec div→03 · complement1 - p with exact decimalsbigdec sum→04 · checkSum of ln(1 - k/365)num sum→05 · hashsqrt(2 ln2 2^64)bigdec sqrt

Script

admin

#1. Exact probability that 23 birthdays are all different: 365!/342! / 365^23;
-> "[ways]" (arith npr 365 23);
-> "[all]" (bigdec pow 365 23 80);
-> "[pno]" (bigdec div [ways] [all] 30);
#2. Probability of a collision = 1 - pno;
-> "[pcol]" (bigdec sum (concat "[1, " (bigdec negate [pno]) "]"));
#3. Same with lgamma, with a sum of logarithms, and the approximation 1 - exp of -k^2/2N;
-> "[plg]" (math eval "1-exp(lgamma(366)-lgamma(343)-23*ln(365))");
-> "[psum]" (math calc (concat "1-exp(" (num sum "ln(1-k/365)" "k" 1 22) ")"));
-> "[papp]" (math calc "1-exp(-23^2/(2*365))");
#4. 64-bit hash: number of hashes for a 50 percent collision chance;
-> "[k50]" (bigdec sqrt (math calc "2*ln(2)*2^64") 6);
concat "pairs = " (arith ncr 23 2) ", P(collision) = " (bigdec precision [pcol] 12) " (lgamma: " [plg] ", sum: " [psum] ", approx: " (math round [papp] 4) "); 64-bit hash: " [k50] " hashes, about 2^32 = " (arith isqrt (bigdec pow 2 64 30))

Result

mentdb

pairs = 253, P(collision) = 0.507297234324 (lgamma: 0.507297234324094, sum: 0.5072972343239854, approx: 0.5155); 64-bit hash: 5056940000 hashes, about 2^32 = 4294967296

Go further

Find the smallest group size with a probability above 99 % with num solve on the lgamma formula
Count the pairs of a larger group with arith ncr

executed on MentDB

Signing a document hash and the avalanche effect

Hash a lease contract with SHA-256, sign the hash with a fresh 2048-bit key pair, verify the signature, then change one digit of the rent: the new hash differs in about 15/16 of its hex digits and the signature no longer verifies.

Pipeline

01 · hashSHA-256 fingerprintstring sha_256→02 · keys2048-bit key pair in memorystring encode_sign_generate_keypair→03 · signSign the hashstring encode_sign→04 · verifyVerify, then verify a tampered copystring decode_sign_verify

Script

admin

#1. Fingerprint of a contract with SHA-256;
-> "[doc]" "Lease 2026-114: rent 1250 EUR per month, deposit 2500 EUR, signed in Saint-Denis";
-> "[h]" (string sha_256 [doc]);
#2. Signature key pair of 2048 bits, kept in memory;
json load "rx_tu1_keys" (string encode_sign_generate_keypair "2048");
#3. Sign the hash, verify it with the public key;
-> "[sig]" (string encode_sign [h] (json select "rx_tu1_keys" "/privateKey"));
-> "[ok]" (string decode_sign_verify [h] [sig] (json select "rx_tu1_keys" "/publicKey"));
#4. Tamper with one digit of the rent: new hash, the old signature fails;
-> "[h2]" (string sha_256 (string replace [doc] "1250" "1150"));
-> "[bad]" (string decode_sign_verify [h2] [sig] (json select "rx_tu1_keys" "/publicKey"));
#5. Avalanche effect: hex digits that differ between the two hashes;
-> "[d]" 0;
for (-> "[i]" 0) (< [i] 64) (++ "[i]") {
	if (!= (string substring [h] [i] (+ [i] 1)) (string substring [h2] [i] (+ [i] 1))) {++ "[d]";};
};
concat "SHA-256 = " [h] " (" (string length [h]) " hex digits = " (* 4 (string length [h])) " bits); signature valid = " [ok] "; tampered contract valid = " [bad] "; hex digits changed by one character = " [d] "/64 (expected 60)"

Result

mentdb

SHA-256 = ca8ff4df66d1237b75711e81d8b47ea6d7cff93ec9671f3e1e4cb4da4f1feb9a (64 hex digits = 256 bits); signature valid = 1; tampered contract valid = 0; hex digits changed by one character = 61/64 (expected 60)

Go further

Authenticate a webhook payload with a shared secret: string hmac_sha256
Encrypt the contract itself for one reader with string encode_rsa_generate_keypair and string encode_rsa

executed on MentDB

Password entropy, brute-force time and bcrypt

Compare a random 12-character password and a 6-word diceware passphrase: entropy in bits, mean time to crack with a fast hash against bcrypt cost 12, then hash the passphrase with bcrypt and verify a good and a wrong guess.

Pipeline

01 · entropyL.log2 of the alphabet sizemath calc→02 · attackMean time 2^(H-1) / ratemath round_sig→03 · hashbcrypt cost 12, random saltstring bcrypt_hash→04 · verifyGood and wrong passwordstring bcrypt_verify

Script

admin

#1. Entropy of a random 12-character password over the 94 printable ASCII and of a 6-word diceware passphrase;
-> "[H1]" (math calc "12*log(94)/log(2)");
-> "[H2]" (math calc "6*log(7776)/log(2)");
#2. Mean brute-force time: half the key space at 1e11 SHA-256 per s on a GPU rig, in years;
-> "[yr]" (math calc "365.25*86400");
-> "[t1]" (math calc "2^([H1]-1)/1e11/[yr]");
#3. bcrypt cost 12: 2^12 key expansions, about 1500 guesses per s on the same rig;
-> "[t2]" (math calc "2^([H2]-1)/1500/[yr]");
-> "[hash]" (string bcrypt_hash "correct horse battery staple" 12);
-> "[ok]" (string bcrypt_verify "correct horse battery staple" [hash]);
-> "[ko]" (string bcrypt_verify "Correct horse battery staple" [hash]);
concat "12 chars: " (math round [H1] 1) " bits, " (math round_sig [t1] 3) " years with SHA-256; 6 words: " (math round [H2] 1) " bits, " (math round_sig [t2] 3) " years with bcrypt; hash prefix " (string substring [hash] 0 7) ", length " (string length [hash]) ", good password = " [ok] ", wrong case = " [ko]

Result

mentdb

12 chars: 78.7 bits, 75400 years with SHA-256; 6 words: 77.5 bits, 2340000000000 years with bcrypt; hash prefix $2a$12$, length 60, good password = 1, wrong case = 0

Go further

Store a salted fingerprint for comparison with string sha_512
Generate random test passwords with string generate_random_str and measure their length with string length

executed on MentDB

Two-time pad: breaking a reused one-time key

Two messages were encrypted with the same one-time pad. The script XORs the bytes, shows that c1 xor c2 = p1 xor p2 (the key cancels) and recovers the second message from a guessed crib.

Pipeline

01 · codesCharacter codesstring ascii→02 · xorByte-wise XORmath bit_xor→03 · hexCiphertext in hexadecimalstring int_to_hex→04 · recoverp2 = c1 xor c2 xor p1string char

Script

admin

#1. Two messages encrypted with the SAME one-time pad key, a classic operator mistake;
-> "[p1]" "ATTACK AT DAWN"; -> "[p2]" "RETREAT AT TEN";
-> "[key]" "Q7#kP!z9@Lm2&x";
-> "[c1]" ""; -> "[c2]" ""; -> "[x]" ""; -> "[rec]" "";
for (-> "[i]" 0) (< [i] (string length [p1])) (++ "[i]") {
	-> "[k]" (string ascii (string substr [key] [i] (+ [i] 1)));
	-> "[a]" (math bit_xor (string ascii (string substr [p1] [i] (+ [i] 1))) [k]);
	-> "[b]" (math bit_xor (string ascii (string substr [p2] [i] (+ [i] 1))) [k]);
	-> "[c1]" (concat [c1] (string lpad (string int_to_hex [a]) "0" 2));
	-> "[c2]" (concat [c2] (string lpad (string int_to_hex [b]) "0" 2));
	#2. The attacker XORs the two ciphertexts: the key cancels, c1 xor c2 = p1 xor p2;
	-> "[x]" (concat [x] (string lpad (string int_to_hex (math bit_xor [a] [b])) "0" 2));
	#3. Crib dragging: a guessed word of p1 gives p2 directly;
	-> "[rec]" (concat [rec] (string char (math bit_xor (math bit_xor [a] [b]) (string ascii (string substr [p1] [i] (+ [i] 1))))));
};
concat "c1 = " [c1] [_n_] "c2 = " [c2] [_n_] "c1 xor c2 = " [x] [_n_] "with the crib ATTACK AT DAWN the second message reads: " [rec]

Result

mentdb

c1 = 1063772a136a5a78146c29737136
c2 = 0372773915602e1901184d666336
c1 xor c2 = 13110013060a7461157464151200
with the crib ATTACK AT DAWN the second message reads: RETREAT AT TEN

Go further

Slide a short crib like " AT " along c1 xor c2 to find where it fits
Encode the ciphertexts in Base64 with string encode_b64

executed on MentDB

Period and balance of an 8-bit LFSR keystream

A Galois LFSR with the primitive polynomial x^8+x^6+x^5+x^4+1 (mask 0xB8) is clocked until it returns to its seed. The script checks the maximal period 255, the 128/127 balance of ones and zeros and gives the first keystream byte.

Pipeline

01 · maskFeedback mask from hexstring hex_to_int→02 · bitOutput bitmath bit_and→03 · shiftShift rightmath trunc→04 · feedbackXOR with the maskmath bit_xor→05 · bytePack the bitsmath bit_or

Script

admin

#1. 8-bit Galois LFSR, polynomial x^8+x^6+x^5+x^4+1, mask 0xB8, seed 0x01;
-> "[mask]" (string hex_to_int "B8"); -> "[s]" 1; -> "[n]" 0; -> "[ones]" 0; -> "[byte]" 0;
#2. Clock it until the state comes back to the seed;
while (or (== [n] 0) (!= [s] 1)) {
	-> "[bit]" (math bit_and [s] 1);
	-> "[ones]" (+ [ones] [bit]);
	if (< [n] 8) { -> "[byte]" (math bit_or (* [byte] 2) [bit]); };
	-> "[s]" (math trunc (/ [s] 2));
	if (== [bit] 1) { -> "[s]" (math bit_xor [s] [mask]); };
	++ "[n]";
};
#3. A maximal-length LFSR has period 2^8-1 and 128 ones for 127 zeros;
concat "period = " [n] " (maximal = " (math calc "2^8-1") "), ones = " [ones] ", zeros = " (- [n] [ones]) ", first keystream byte = 0x" (string lpad (string int_to_hex [byte]) "0" 2)

Result

mentdb

period = 255 (maximal = 255), ones = 128, zeros = 127, first keystream byte = 0x8e

Go further

Try a non-primitive mask such as 0xB4 and watch the period drop
Combine two LFSRs with math bit_and as in the Geffe generator

executed on MentDB

Key space and unicity distance of classical ciphers

How much ciphertext does a cryptanalyst need before only one key fits? The script computes the key entropy of the substitution, Playfair and Vigenere ciphers with the log-Gamma function and divides by the redundancy of English.

Pipeline

01 · entropylog2 n! = lngamma(n+1)/ln 2math lngamma→02 · factorial26! with the Gamma functionmath gamma→03 · redundancyD = log2 26 - 1.5math calc→04 · unicityU = H(K)/Dmath round

Script

admin

#1. Key space of classical ciphers in bits, log2 n! = lngamma n+1 / ln 2;
-> "[Hsub]" (math calc (concat (math lngamma 27) "/ln(2)"));
-> "[Hplay]" (math calc (concat (math lngamma 26) "/ln(2)"));
-> "[Hvig]" (math calc "10*log(26)/log(2)");
#2. 26! exactly with the Gamma function;
-> "[fact]" (math gamma 27);
#3. Redundancy of English D = log2 26 - 1.5 bits per letter, unicity distance U = H K / D;
-> "[D]" (math calc "log(26)/log(2)-1.5");
concat "26! = " [fact] "; unicity distance: substitution " (math round (math calc "[Hsub]/[D]") 1) " letters (H = " (math round [Hsub] 1) " bits), Playfair " (math round (math calc "[Hplay]/[D]") 1) " letters, Vigenere key of 10 " (math round (math calc "[Hvig]/[D]") 1) " letters, DES " (math round (math calc "56/[D]") 1) " letters"

Result

mentdb

26! = 4.0329146112660565E26; unicity distance: substitution 27.6 letters (H = 88.4 bits), Playfair 26.1 letters, Vigenere key of 10 14.7 letters, DES 17.5 letters

Go further

Compare with AES-128: U = 128 / D
Get the exact 26! with arith factorial

executed on MentDB

Timing side channel of a password check

A password check that stops at the first wrong character leaks timing. The script compares the response times for a wrong and a right first character with a Mann-Whitney test and a z-test against the known baseline of the server.

Pipeline

01 · testNon-parametric two-sample teststat mann_whitney→02 · baselinez-test with a known sigmastat ztest→03 · jitterPopulation variancestat pvariance→04 · leakDifference of the meansstat mean

Script

admin

#1. Response times in microseconds of a password check, 9 requests each;
-> "[wrong]" "[412.1, 409.8, 415.3, 411.0, 408.7, 413.9, 410.4, 412.6, 409.2]";
-> "[right]" "[418.4, 421.0, 416.9, 419.7, 423.2, 417.5, 420.3, 418.8, 422.1]";
#2. Non-parametric comparison: the first character is right when the check takes longer;
-> "[mw]" (stat mann_whitney [wrong] [right]);
#3. z-test of the right-guess series against the known baseline of the server: 411 us, sigma 2.5 us;
-> "[z]" (stat ztest [right] 411 2.5);
#4. Leak size against the jitter;
-> "[leak]" (math calc (concat (stat mean [right]) "-" (stat mean [wrong])));
concat "leak = " (math round [leak] 2) " us for a jitter of " (math round (math sqrt (stat pvariance [wrong])) 2) " us; Mann-Whitney " [mw] "; z-test " [z]

Result

mentdb

leak = 8.32 us for a jitter of 2.09 us; Mann-Whitney {"u": 0, "p_value": 4.122948020616914E-4, "method": "asymptotic"}; z-test {"z": 10.519999999999982, "p_value": 6.987358437602959E-26}

Go further

Fix the leak with a constant-time comparison and run the test again
Compute the number of requests needed for a 1 us leak

executed on MentDB

Hill cipher with a 2 x 2 key matrix

The textbook Hill cipher: key K = [[3, 3], [2, 5]] modulo 26 encrypts HELP. The script encrypts with a matrix product, checks that det K is invertible modulo 26 and builds the decryption matrix.

Pipeline

01 · encodeLetters to numbersstring ascii→02 · encryptC = K.Pmatrix mul→03 · reduceModulo 26arith irem→04 · detDeterminant of Kmatrix det→05 · inversedet^-1 mod 26arith invmod

Script

admin

#1. Hill cipher, key K = 3 3 / 2 5 modulo 26, plaintext HELP as two columns HE and LP;
-> "[K]" "[[3, 3], [2, 5]]";
-> "[P]" (concat "[[" (- (string ascii "H") 65) ", " (- (string ascii "L") 65) "], [" (- (string ascii "E") 65) ", " (- (string ascii "P") 65) "]]");
#2. Encrypt: C = K.P mod 26, then back to letters column by column;
-> "[C]" (matrix mul [K] [P]);
-> "[ct]" "";
for (-> "[j]" 1) (<= [j] 2) (++ "[j]") {
	for (-> "[i]" 1) (<= [i] 2) (++ "[i]") { -> "[ct]" (concat [ct] (string char (+ 65 (arith irem (matrix get [C] [i] [j]) 26)))); };
};
#3. The key is valid only if det K is invertible modulo 26;
-> "[det]" (math round (matrix det [K]) 0);
-> "[dinv]" (arith invmod [det] 26);
#4. Decryption key K^-1 = det^-1 x adj K, then check K^-1.K = I mod 26;
-> "[Ki]" (matrix scalar_mul "[[5, -3], [-2, 3]]" [dinv]);
-> "[I]" (matrix mul [Ki] [K]);
concat "P = " [P] ", K.P = " [C] ": ciphertext " [ct] "; det K = " [det] ", gcd with 26 = " (arith gcd [det] 26) ", det^-1 mod 26 = " [dinv] "; K^-1 = " [Ki] " = [[" (arith irem (matrix get [Ki] 1 1) 26) ", " (arith irem (matrix get [Ki] 1 2) 26) "], [" (arith irem (matrix get [Ki] 2 1) 26) ", " (arith irem (matrix get [Ki] 2 2) 26) "]] mod 26; K^-1.K mod 26 = [[" (arith irem (matrix get [I] 1 1) 26) ", " (arith irem (matrix get [I] 1 2) 26) "], [" (arith irem (matrix get [I] 2 1) 26) ", " (arith irem (matrix get [I] 2 2) 26) "]]"

Result

mentdb

P = [[7, 11], [4, 15]], K.P = [[33,78],[34,97]]: ciphertext HIAT; det K = 9, gcd with 26 = 1, det^-1 mod 26 = 3; K^-1 = [[15,-9],[-6,9]] = [[15, 17], [20, 9]] mod 26; K^-1.K mod 26 = [[1, 0], [0, 1]]

Go further