Cryptography

References

• Journey into cryptography, on Khan Academy

Key Lengths

RSA

See recommendations from Bruce Schneier in Applied Cryptography (§7.2, [1]). See also [2]

Recommended public-key key lengths (in bits) — Source: Applied Cryptography, 2nd edition

Year	vs. industry	vs. Corporate	vs. Government
1995	768	1280	1536
2000	1024	1280	1536
2005	1280	1536	2048
2010	1280	1536	2048
2015	1536	2048	2048

Crypto performance

Summary

Src	Algorithm	Time	RAM	Code	CPU	Freq	Board	Notes
[1]	SHA-256 on 1024B	0.6 ms			ARM Cortex-M3	96 MHz	NXP LPC1768
[1]	SHA-512 on 1024B	1.4 ms			ARM Cortex-M3	96 MHz	NXP LPC1768
[1]	AES-CBC-128 on 1024B	0.7 ms			ARM Cortex-M3	96 MHz	NXP LPC1768
[1]	AES-CBC-192 on 1024B	0.8 ms			ARM Cortex-M3	96 MHz	NXP LPC1768
[1]	AES-CBC-256 on 1024B	0.9 ms			ARM Cortex-M3	96 MHz	NXP LPC1768
[1]	AES-GCM-128 on 1024B	1.8 ms			ARM Cortex-M3	96 MHz	NXP LPC1768
[1]	AES-GCM-192 on 1024B	1.9 ms			ARM Cortex-M3	96 MHz	NXP LPC1768
[1]	AES-GCM-256 on 1024B	2.0 ms			ARM Cortex-M3	96 MHz	NXP LPC1768
[1]	AES-CCM-128 on 1024B	1.7 ms			ARM Cortex-M3	96 MHz	NXP LPC1768
[1]	AES-CCM-192 on 1024B	1.9 ms			ARM Cortex-M3	96 MHz	NXP LPC1768
[1]	AES-CCM-256 on 1024B	2.1 ms			ARM Cortex-M3	96 MHz	NXP LPC1768
[1]	NIST P-192 ECDHE	229.0 ms			ARM Cortex-M3	96 MHz	NXP LPC1768	Optim: window=7
[1]	NIST P-224 ECDHE	303.0 ms			ARM Cortex-M3	96 MHz	NXP LPC1768	Optim: window=7
[1]	NIST P-256 ECDHE	432.0 ms			ARM Cortex-M3	96 MHz	NXP LPC1768	Optim: window=7
[1]	NIST P-192 ECDSA Verify	251.0 ms			ARM Cortex-M3	96 MHz	NXP LPC1768	Optim: window=7
[1]	NIST P-192 ECDSA Sign	66.0 ms			ARM Cortex-M3	96 MHz	NXP LPC1768	Optim: window=7
[1]	NIST P-224 ECDSA Verify	329.0 ms			ARM Cortex-M3	96 MHz	NXP LPC1768	Optim: window=7
[1]	NIST P-256 ECDSA Verify	458.0 ms			ARM Cortex-M3	96 MHz	NXP LPC1768	Optim: window=7
[1]	NIST P-256 ECDSA Sign	122.0 ms			ARM Cortex-M3	96 MHz	NXP LPC1768	Optim: window=7
[1]	NIST P-384 ECDSA Verify	806.0 ms			ARM Cortex-M3	96 MHz	NXP LPC1768	Optim: window=7
[1]	NIST P-521 ECDSA Verify	1414.0 ms			ARM Cortex-M3	96 MHz	NXP LPC1768	Optim: window=7
[1]	NIST P-192 ECDHE	796.0 ms			ARM Cortex-M0	48 MHz	ST Nucleo F091	Optim: NIST, fixed point, window=7
[1]	NIST P-224 ECDHE	1119.0 ms			ARM Cortex-M0	48 MHz	ST Nucleo F091	Optim: NIST, fixed point, window=7
[1]	NIST P-256 ECDHE	1672.0 ms			ARM Cortex-M0	48 MHz	ST Nucleo F091	Optim: NIST, fixed point, window=7
[1]	NIST P-384 ECDHE	3254.0 ms			ARM Cortex-M0	48 MHz	ST Nucleo F091	Optim: NIST, fixed point, window=7
[1]	NIST P-512 ECDHE	6537.0 ms			ARM Cortex-M0	48 MHz	ST Nucleo F091	Optim: NIST, fixed point, window=7
[1]	NIST P-192 ECDSA Sign	225.0 ms			ARM Cortex-M0	48 MHz	ST Nucleo F091	Optim: NIST, fixed point, window=7
[1]	NIST P-224 ECDSA Sign	224.0 ms			ARM Cortex-M0	48 MHz	ST Nucleo F091	Optim: NIST, fixed point, window=7
[1]	NIST P-256 ECDSA Sign	459.0 ms			ARM Cortex-M0	48 MHz	ST Nucleo F091	Optim: NIST, fixed point, window=7
[1]	NIST P-384 ECDSA Sign	384.0 ms			ARM Cortex-M0	48 MHz	ST Nucleo F091	Optim: NIST, fixed point, window=7
[1]	NIST P-512 ECDSA Sign	521.0 ms			ARM Cortex-M0	48 MHz	ST Nucleo F091	Optim: NIST, fixed point, window=7
[1]	NIST P-192 ECDSA Verify	845.0 ms			ARM Cortex-M0	48 MHz	ST Nucleo F091	Optim: NIST, fixed point, window=7
[1]	NIST P-224 ECDSA Verify	1185.0 ms			ARM Cortex-M0	48 MHz	ST Nucleo F091	Optim: NIST, fixed point, window=7
[1]	NIST P-256 ECDSA Verify	1759.0 ms			ARM Cortex-M0	48 MHz	ST Nucleo F091	Optim: NIST, fixed point, window=7
[1]	NIST P-384 ECDSA Verify	3361.0 ms			ARM Cortex-M0	48 MHz	ST Nucleo F091	Optim: NIST, fixed point, window=7
[1]	NIST P-512 ECDSA Verify	6693.0 ms			ARM Cortex-M0	48 MHz	ST Nucleo F091	Optim: NIST, fixed point, window=7
[1]	NIST P-192 ECDHE	1155.0 ms			ARM Cortex-M3	32 MHz	ST Nucleo L152RE	Optim: window=7
[1]	NIST P-224 ECDHE	1609.0 ms			ARM Cortex-M3	32 MHz	ST Nucleo L152RE	Optim: window=7
[1]	NIST P-256 ECDHE	2399.0 ms			ARM Cortex-M3	32 MHz	ST Nucleo L152RE	Optim: window=7
[2]	NIST P-192 ECDH	438.9 ms			ARM Cortex-M0 32cy mult	48 MHz	NXP LPC1114	No optim
[2]	NIST P-192 ECDH	175.7 ms		2170 B	ARM Cortex-M0 32cy mult	48 MHz	NXP LPC1114	Square + ASM optim
[2]	NIST P-256 ECDH	465.1 ms		2512 B	ARM Cortex-M0 32cy mult	48 MHz	NXP LPC1114	Square + ASM optim
[2]	NIST P-384 ECDH	1370.3 ms		2244 B	ARM Cortex-M0 32cy mult	48 MHz	NXP LPC1114	Square + ASM optim
[2]	NIST P-192 ECDSA Verify	217.1 ms		3014 B	ARM Cortex-M0 32cy mult	48 MHz	NXP LPC1114	Square + ASM optim
[2]	NIST P-256 ECDSA Verify	555.2 ms		3334 B	ARM Cortex-M0 32cy mult	48 MHz	NXP LPC1114	Square + ASM optim
[2]	NIST P-384 ECDSA Verify	1576.1 ms		3158 B	ARM Cortex-M0 32cy mult	48 MHz	NXP LPC1114	Square + ASM optim
[1]	NIST P-256 ECDSA Sign	122.0 ms	4568 B		ARM Cortex-M3	96 MHz	NXP LPC1768	Optim: NIST, FP, W=6
[1]	NIST P-256 ECDSA Sign	378.0 ms	2972 B		ARM Cortex-M3	96 MHz	NXP LPC1768	Optim: NIST, W=2
[1]	NIST P-256 ECDSA Verify	458.0 ms	5380 B		ARM Cortex-M3	96 MHz	NXP LPC1768	Optim: NIST, FP, W=6
[1]	NIST P-256 ECDSA Verify	759.0 ms	3072 B		ARM Cortex-M3	96 MHz	NXP LPC1768	Optim: NIST, W=2
[1]	NIST P-256 ECDHE	431.0 ms	5012 B		ARM Cortex-M3	96 MHz	NXP LPC1768	Optim: NIST, FP, W=6
[1]	Curve15519 ECDHE	552.0 ms			ARM Cortex-M0+	48 MHz	FRDM-KL46Z	Google-donna impl
[1]	Curve15519 ECDHE	94.0 ms			ARM Cortex-M3	96 MHz	NXP LPC1768	Google-donna impl
[1]	Curve15519 ECDHE	58.0 ms			ARM Cortex-M4	120 MHz	FRDM-K64F	Google-donna impl

Sources:

• * means result derived (extrapolated) from results in the given source.
• [1] Hugo Vincent, Hannes Tschofenig and Manuel Pegourie-Gonnard, Performance of State-of-the-Art Cryptography on ARM-based Microprocessors, July 21, 2015. https://csrc.nist.gov/csrc/media/events/lightweight-cryptography-workshop-2015/documents/presentations/session7-vincent.pdf
• [2] Ken MacKay, micro-ecc, https://github.com/kmackay/micro-ecc/tree/old.

SW Speed on ARM

Hash Algorithm Name Throughput (kB/s) SHA-1 1915 MD5 3516 Symmetric algorithms Name Throughput (kB/s) AES-CBC 825 AES-ECB 874 AES-CCM, CT only 373 AES-CCM, AD only 816 3DES-CBC 326 3DES-CTR 317 3DES-ECB 333

Asymmetric, Encrypt/Decrypt Name Time (s) RSA-1024 encrypt 0.01 RSA-1024 decrypt 0.27 RSA-2048 encrypt 0.05 RSA-2048 decrypt 2.13

Asymmetric, Sign/Verify Name Time (s) RSA-1024 sign 0.27 RSA-1024 verify 0.01 RSA-2048 sign 2.13 RSA-2048 verify 0.05 DSA-1024 sign 0.17 DSA-1024 verify 0.33

Diffie-Hellman Modulus Size (b) Private Key size (b) Time (s) 1024 160 0.17 1024 1024 1.08 2048 224 0.93 2048 2048 8.48

More bench

• https://realtimelogic.com/products/sharkssl/Cortex-M3/

(see SharkSSL_Benchmark_for_ARM_Cortex_M3.pdf)

• https://csrc.nist.gov/csrc/media/events/lightweight-cryptography-workshop-2015/documents/presentations/session7-vincent.pdf

(Performance for AES, ECC, ECDH, ECDSA, EdDSA on Cortex M0/M3 ...)

HW Speed on NXP SMX P5Cx08x

Based on linecard figures:

Algo	Size	Sign	Verify
RSA	1024-bit	99 ms (CRT)	2 ms
ECC	192-bit	20 ms	30 ms
DES3		<40 µs	<40 µs
AES	128/192/256	12/13/15 µs	12/13/15 µs

Crypto Libraries

libgcrypt

libgcrypt is a very nice C crypto library. It is used in gnupg.

• Big numbers.
• symmetric crypto.
• Asymmetric crypto (RSA, ECC).
• Fast or secure implementation

Resources:

• libgcrypt git repository

Reading these tests is the best way to understand how to use the library.

• libgcrypt reference manual

NTRU

• A native crypto library on ARM MCU (i.e. embedded platform).
• Check http://ics.nxp.com/support/training/ntru.encryption.overview/pdf/ntru.encryption.overview.pdf

BouncyCastle

• Free Java crypto library

Crypto++

• A crypto library in C++

Public Domain libraries

• Crypto-algorithms (github) — basic implementations from Brad Conte of various algorithms.
• libtomcrypt (also here) (tomcrypt)

Crypto calculators

Online

• [http://www.unsw.adfa.edu.au/~lpb/src/AEScalc/AEScalc.html AES Calculator (java applet)

OpenSSL

#Computing AES-128 CBC No padding
echo "000102030405060708090a0b0c0d0e0f000102030405060708090a0b0c0d0e0f" | xxd -r -p |openssl aes-128-cbc -iv 0 -K 01010101020202020303030304040404 -nopad \
| xxd -p

#Advanced mumbo-jambo
echo $(( (0x$(echo "1111111111f2222222222f3333333333f4444444444f5555555555f6666666666f7777777777f8888888888f9999999999f0000000000f80"\
|xxd -r -p |openssl des-cbc -iv 0 -K 0102030405060708 -nopad |xxd -p|tail -c 6) & 0x03ffff) + (0x10*2**18) ))

AES

AES-GCM

• NIST SP800-38D, the official standard (PDF).
• Galois/Counter Mode (Wikipedia)

Nicer illustration.

• aes-gcm C implementation (wpa_supplicant_8) (also here)

A clean C implementation.

• Authentication Failures in NIST version of GCM.

In particular describes the "Forbidden Attack" that leads to retrieving H when repeating the IV.

• Authentication Weaknesses in GCM (Ferguson)

Describes two forgeries attacks and how to retrieve H, ie. the zero block encrypted with the key. Retrieving H means total loss of authentication assurance.

RSA

References

• ✔Dan Boneh, Twenty Years of Attacks on the RSA Cryptosystem, February 1999, Notices of the AMS, http://www.ams.org/notices/199902/boneh.pdf
• ✔Don Coppersmith, Small solutions to polynomial equations, and low exponent rsa vulnerabilities, Journal of Cryptology 10 (1997), no. 4, 233–260. 1997-JOC-Vol10-4-002.pdf
  This paper covers the 2 papers:
  • Don Coppersmith, Finding a Small Root of a Bivariate Integer Equation; Factoring with High Bits Known, U. Maurer (Ed.): Advances in Cryptology - EUROCRYPT '96, LNCS 1070, pp. 178-189, 1996. 1996-EUROCRYPT-016.pdf
  • Don Coppersmith, Finding a Small Root of a Univariate Modular Equation, U. Maurer (Ed.): Advances in Cryptology - EUROCRYPT ’96, LNCS 1070, pp. 155-165, 1996. 1996-EUROCRYPT-014.pdf
• ? Seong-Min Hong, Sang-Yeop Oh, and Hyunsoo Yoon, New Modular Multiplication Algorithms for Fast Modular Exponentiation, Proceeding EuroCrypt'96 (U. Maurer,ed.), Lecture Notes in Computer Science, vol. 1070, Springer-Verlag, 1996, pp. 166--177.
• ~ Alexander May, New RSA Vulnerabilities Using Lattice Reduction Methods, PhD thesis, University of Paderborn, October 2003. http://www.cs.uni-paderborn.de/uploads/tx_sibibtex/bp.pdf

(Coppersmith method, breaking RSA from partial knowledge of message, partial export of private exponent or prime factors, variants of RSA...)

• ~ Leo Reyzin, Notes for lecture 8 — Chinese Remainder Theorem and Blum-Blum-Shub PRG, Fall 2004, BU CAS CS 538, http://www.cs.bu.edu/~reyzin/teaching/f04cs538/notes8.pdf
• ~ Scott A. Vanstone and Robert J. Zuccherato, Short RSA Keys and Their Generation, J. Cryptology 8 (1995), no. 2, 101--114. 1995-JOC-Vol08-2-003.pdf

(Generate modulus with given modulus bit pattern, but the methods in this paper are inefficient and broken - better alternatives below)

• ? RSA Moduli with a Predetermined Portion: Techniques and Applications, Information Security Practice and Experience (ISPEC 2008), vol. 4991 of Lecture Notes in Computer Science, pp. 116{130, Springer, 2008. http://joye.site88.net/papers/Joy08rsacompr.pdf
• ~ Arjen K. Lenstra. Generating RSA moduli with a predetermined portion. In Advances in Cryptology - ASIACRYPT'98, volume 1514 of Lecture Notes in Computer Science, pages 1{10. Springer, 1998.

(Implement obvious method; pick n' with the fixed pattern. pick p random prime, round n' up to nearest multiple, compute q' s.t. n'=pq', find nearest prime q, compute n=pq)

• ? Jingjing Wang, Attacks against RSA Cryptosystems in Thirty Years, June 2011, http://cis.sjtu.edu.cn/download/d/df/RSA_Attacks.pdf

Publications by authors

• J.S. Coron — many interesting articles.
• X9 standards — See nice summary from RSA Laboratories.

Generate RSA Keys

Under Linux, Install package racoon. Then you can use plainrsa-gen to generate a RSA key pair:

sudo plainrsa-gen -b 512 -e 65537

$ plainrsa-gen -b 512 -e 65537
: RSA	{
	# RSA 256 bits
	# pubkey=0sAwEAAZI52+jaMTOU7BVFJfR3XO0/HNuagkdwnODaOEz5Vl57
	Modulus: 0x9239dbe8da313394ec154525f4775ced3f1cdb9a8247709ce0da384cf9565e7b
	PublicExponent: 0x010001
	PrivateExponent: 0x6a32c54916f676dce89d060c6bc128e6384ddd3480ebc38abb26b06bbbc39ee9
	Prime1: 0xc2ebb37492f49c2536d1425a1e98bced
	Prime2: 0xc00bedf79253f91bc219fb076fdb8407
	Exponent1: 0x6a70e3d268dd82d71f942e33a039b011
	Exponent2: 0x143e2dab36e55b10adf90718d59591e9
	Coefficient: 0x3d988139c172a1b329850a294347b99e
  }

Another solution is to use openssl:

openssl genrsa 256 > private.pem

Generating RSA private key, 256 bit long modulus
......+++++++++++++++++++++++++++
.............+++++++++++++++++++++++++++
e is 65537 (0x10001)

This produce a private key in .PEM format

cat private.pem

-----BEGIN RSA PRIVATE KEY-----
MIGqAgEAAiEArBZ8o1wXjfGaJoYyEw20HewqLGTJ6mI3i2ntexqztc8CAwEAAQIg
ObfNFAmGSPB40GUAFI3rE/VQokHFKOpqBnu2/fEGwdECEQDX5IwHMajhOd/e4h1O
J//ZAhEAzA6pCZiM+kcFPDo/S/wB5wIQAlGyL2GZLtIwVXSYW/6SAQIQZQ/VtETz
fXjzJNMMSkuzfQIRAM0VX/ffPwICmDEJGxg5YqY=
-----END RSA PRIVATE KEY-----

See below for how to display components or RSA keys.

The following script will generate 10 keys for each size in the set {1024 1536 1664 1792 1920 2048 2304 2560 2816 3072 3328 3584 3840 4096}:

#! /bin/bash
#
# Script to generate a batch of RSA keys of various length
#

function gen-one-key()
{
	openssl genrsa $1 | openssl pkcs8 -topk8 -nocrypt -outform DER -out "$2-pk8.der"
	openssl asn1parse -inform DER -in "$2-pk8.der" > "$2-pk8.txt"
	echo -e "\n############### Content of RSA Private Key object ###############\n" >> "$2-pk8.txt"
	openssl pkcs8 -inform DER -in "$2-pk8.der" -nocrypt | openssl asn1parse >> "$2-pk8.txt"
}

for keylength in 1024 1536 1664 1792 1920 2048 2304 2560 2816 3072 3328 3584 3840 4096; do
	for keyidx in $(seq 1 10); do
		keyname="rsakey-${keylength}b-$(printf '%02d' $keyidx)"
		echo "########## gen-one-key $keylength \"$keyname\""
		gen-one-key $keylength "$keyname"
	done
done

View and convert RSA Keys

Use openssl rsa -text to display the key

openssl rsa -text <private.pem        # or openssl rsa -in private.pem -text

Private-Key: (256 bit)
modulus:
    00:ac:16:7c:a3:5c:17:8d:f1:9a:26:86:32:13:0d:
    b4:1d:ec:2a:2c:64:c9:ea:62:37:8b:69:ed:7b:1a:
    b3:b5:cf
publicExponent: 65537 (0x10001)
privateExponent:
    39:b7:cd:14:09:86:48:f0:78:d0:65:00:14:8d:eb:
    13:f5:50:a2:41:c5:28:ea:6a:06:7b:b6:fd:f1:06:
    c1:d1
prime1:
    00:d7:e4:8c:07:31:a8:e1:39:df:de:e2:1d:4e:27:
    ff:d9
prime2:
    00:cc:0e:a9:09:98:8c:fa:47:05:3c:3a:3f:4b:fc:
    01:e7
exponent1:
    02:51:b2:2f:61:99:2e:d2:30:55:74:98:5b:fe:92:
    01
exponent2:
    65:0f:d5:b4:44:f3:7d:78:f3:24:d3:0c:4a:4b:b3:
    7d
coefficient:
    00:cd:15:5f:f7:df:3f:02:02:98:31:09:1b:18:39:
    62:a6
writing RSA key
-----BEGIN RSA PRIVATE KEY-----
MIGqAgEAAiEArBZ8o1wXjfGaJoYyEw20HewqLGTJ6mI3i2ntexqztc8CAwEAAQIg
ObfNFAmGSPB40GUAFI3rE/VQokHFKOpqBnu2/fEGwdECEQDX5IwHMajhOd/e4h1O
J//ZAhEAzA6pCZiM+kcFPDo/S/wB5wIQAlGyL2GZLtIwVXSYW/6SAQIQZQ/VtETz
fXjzJNMMSkuzfQIRAM0VX/ffPwICmDEJGxg5YqY=
-----END RSA PRIVATE KEY-----

... or openssl asn1parse to display the key

openssl asn1parse <private.pem

    0:d=0  hl=3 l= 170 cons: SEQUENCE          
    3:d=1  hl=2 l=   1 prim: INTEGER           :00
    6:d=1  hl=2 l=  33 prim: INTEGER           :AC167CA35C178DF19A268632130DB41DEC2A2C64C9EA62378B69ED7B1AB3B5CF
   41:d=1  hl=2 l=   3 prim: INTEGER           :010001
   46:d=1  hl=2 l=  32 prim: INTEGER           :39B7CD14098648F078D06500148DEB13F550A241C528EA6A067BB6FDF106C1D1
   80:d=1  hl=2 l=  17 prim: INTEGER           :D7E48C0731A8E139DFDEE21D4E27FFD9
   99:d=1  hl=2 l=  17 prim: INTEGER           :CC0EA909988CFA47053C3A3F4BFC01E7
  118:d=1  hl=2 l=  16 prim: INTEGER           :0251B22F61992ED2305574985BFE9201
  136:d=1  hl=2 l=  16 prim: INTEGER           :650FD5B444F37D78F324D30C4A4BB37D
  154:d=1  hl=2 l=  17 prim: INTEGER           :CD155FF7DF3F02029831091B183962A6

Use option -pubout to extract public keys from private key (PEM format):

openssl rsa -in private.pem -pubout -out public.pem

writing RSA key

To view a public key from a PEM file, use options -pubin -text

openssl rsa -in public.pem -pubin -text

Public-Key: (256 bit)
Modulus:
    00:ac:16:7c:a3:5c:17:8d:f1:9a:26:86:32:13:0d:
    b4:1d:ec:2a:2c:64:c9:ea:62:37:8b:69:ed:7b:1a:
    b3:b5:cf
Exponent: 65537 (0x10001)
writing RSA key
-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAKwWfKNcF43xmiaGMhMNtB3sKixkyepi
N4tp7Xsas7XPAgMBAAE=
-----END PUBLIC KEY-----

Factor RSA modulus

Using Sage (see [3]):

# RSA 192-bit
mod192=0xbdd0fcbce5f05aae8049f0699443b575c3119a00f712fd67
print "Factoring RSA 192-bit modulus"
print "mod192=",mod192
print "Using factor():"
time mod192.factor()
print "Using ecm.factor():"
time ecm.factor(mod192)

This gives:

  Factoring RSA 192-bit modulus
  mod192= 4654283518078358737104805100407304944292151641869472955751
  Using factor():
  67662411935248621468167032027 * 68786840210963828271650042213
  Time: CPU 12.14 s, Wall: 13.55 s
  Using ecm.factor():
  [67662411935248621468167032027, 68786840210963828271650042213]
  Time: CPU 0.00 s, Wall: 62.04 s

Other method based on the General Number Field Sieve (GNFS). There are several free ports on Linux:

• [4], links to other projects like GGNFS, MSIEVE, YAFU, up-to-date binaries, Python...
  • Windows Factoring Software Binaries for GGNFS, GMP-ECM, MSIEVE, YAFU.
• YAFU, Yet Another Factorization Utility. Fastest for small number (< 90 digits). Also provides binaries for Windows & Linux!
• Msieve - One of the best apparently - see here and there
  • See an excellent guide here, and compiled version here
• GGNFS, which is based on GMP library.
• kmGNFS - A General Number Field Sieve (GNFS) Implementation, based on NTL library.
• factor-by-gnfs
• Flint documentation refers to a program mpQS that would implement the quadratic sieve method.

For instance, using YAFU. First factorization is for RSA 192-bit, second is for RSA 256-bit:

$ unzip yafu-1.19.2.zip
$ cd yafu-1.19.2
$ chmod +X yafu-*
$ ./yafu-64k-linux64

>> factor(4654283518078358737104805100407304944292151641869472955751)

factoring 4654283518078358737104805100407304944292151641869472955751

...

Total factoring time = 8.2085 seconds

***factors found***

PRP29 = 67662411935248621468167032027
PRP29 = 68786840210963828271650042213

or even better with multi-threading:

$ echo "factor(67838243504816110168272546172330833508240822615334162379358840774428225237019)" | ./yafu-64k-linux64 -threads 24

factoring 67838243504816110168272546172330833508240822615334162379358840774428225237019

...

Total factoring time = 17.05 seconds

***factors found***

PRP39 = 255668459558430779725491264793137830843
PRP39 = 265336770996237319406691555335704774433

Elliptic Curve Cryptography (ECC)

Standards:

• NIST FIPS 186-4, Digital Signature Standard

Specifies the recommended curves for ECC (NIST Curve P-256, Curve P-384...).

• RFC6979 - Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA)

About deterministic (EC)DSA, including nice test vectors.

Very nice introduction by Andrea Corbellini:

• Elliptic Curve Cryptography: a gentle introduction
• Elliptic Curve Cryptography: finite fields and discrete logarithms
• Elliptic Curve Cryptography: ECDH and ECDSA
• Elliptic Curve Cryptography: breaking security and a comparison with RSA

(including nice graphics and visuals with HTML5/Javascript, source available)

ECC Security

• SafeCurves: choosing safe curves for elliptic-curve cryptography (https://safecurves.cr.yp.to/)

References

• point-at-infinity.org - Reference info and test vectors for ECC

• point-at-infinity.org - Test vectors for NIST curves...
• All Hackers Need To Know About Elliptic Curve Cryptography

Curves

• Weierstrass curves — y^2 = x^3 + a*x + b, the most general form.
• Montgomery curves — B*y^2 = x^3 + A*x^2 + x, a subset of curves (~40%).
• Twisted Edwards curves — a*x^2 + y^2 = 1 + d*x^4*y^4, a subset of curves (~40%).

Point coordinates

• Affine coordinates — The standard (x,y) coordinates used in curve's equation. These coordinates must be completed with the point-at-infinity, which has no affine representation.
• Projective coordinates — Triplet (x,y,z). Given affine coordinate (X,Y), we have X=x/z; Y=y/z. Point at infinity has coordinate (0,y,0), ie z=0. Using projective coordinates same modular inverse operation (dividing by z).

Implementations

• A comb method to render ECC resistant against Side Channel Attack, shttps://eprint.iacr.org/2004/342.pdf

Tutorials

• https://curves.ulfheim.net/ — Animated ECC curves

Curve25519, edwards25519, Ed25519, X25519

• X25519 is ECDH on Curve25519.

• Curve25519, see RFC7748.
• On existence of equivalent key, see this StackExchange question. We must find a point Q whose order divides 8, then P and P+Q are public keys that will produce the same shared secret for any private scalar k (clamped scalar as in RFC, ie. multiple of 8).

• Ed25515 is EdDSA on Edwards25519, a variant of Curve25519 (ie. same curve but with transformed coordinates or something).

• See rfc8032.
• Ed25519, see ed25519.py (cr.yp.to).

• https://crypto.stackexchange.com/questions/68026/curve25519s-y-coordinate-of-basepoint-origin

• Curve25519 is a Montgomery curve, and edwards25519 is another one that is birational equivalent.
• X25519 is ECDH built on top of Curve2559. The base point P uses u=9 (v is not used).
• Ed25519 is EdDSA built on top of edwards25519. The base point Q matches P, and we have y=4/5.

• https://cr.yp.to/ecdh.html

Quantum Cryptography

Quantum Verification Problem

• Graduate student solves quantum verification problem
• https://quantumfrontiers.com/2018/08/05/the-quantum-wave-in-computing/
• https://arxiv.org/pdf/1804.01082.pdf

Provably random numbers

• https://arxiv.org/pdf/1804.00640.pdf

Classical Homomorphic Encryption for Quantum Circuits

• https://arxiv.org/pdf/1708.02130.pdf

News

• Breaking RSA with a Quantum Computer - Schneier
• IBM Unveils 400 Qubit-Plus Quantum Processor and Next-Generation IBM Quantum System Two (2022)

Post-Quantum Cryptography

Stateful Hash-based signatures

• NIST SP 800-208 Recomendation for Stateful Hash-Bas Signature Schemes
• XMS and HMSS? RFC?
• Security well understood (against quantum attacks).
• (Very) long-life signatures, but only cover signatures, and limited number of signatures.

• Suitable to eg. secure firmware update.

Code-based cryptography

• Based on error-correcting codes (proposed by McEliece in 1978)
• Quite fast, but very large key sizes (megabytes).
• NIST candidates: Classic McEliece (KEM), NKE, HQC (alternate KEM).

Lattice-based cryptography

• Most finalists in NIST PCQ are LBC.
• Very strong security proofs based on worst-case hardness.
• Shortest Vector Problem.

• Find the shortest non-zero vector in an n-dim lattice.
• Subject to LLL algorithm, but doesn't apply usually (eg. NTRU immune).
• No known quantum algorithms in poly time.

• Two basic hard problems:

• Module-Learning-With-Errors (Module-LWE): problem of finding private key s, given several pairs (a, <a.s> + e), with e error vector.
• Module-Learning-with-Rounding (Module-LWR).

Polynomials Equations over F2

• Fast Exhaustive Search for Polynomial Systems over F2 (Charles Bouillaguet)

Misc Speed Info

HW	LM M/s	NTLM M/s	MD5 M/s	Ref
NVidia Tesla S1070	680	2600	1920	[5]
NVidia GTX 295	250	1330	880-920		[6]
NVidia GTX 285	195	795	570-585		[7]
Intel Q6600	32	87	70

Embedded:

• RSA-KEM-2048 bit: 28us.
• RSA-CERT:

Ciphers

Bilateral ciphers

Example: http://www.cabinetmagazine.org/issues/40/sherman.php

In this example, people on a photograph are forming a coded phrase by facing forward or sideways, using the code:

Sir Francis Bacon Bilateral code

code	meaning	code	meaning	code	meaning	code	meaning
aaaaa	A	aaaab	B	aaaba	C	aaabb	D
aabaa	E	aabab	F	aabba	G	aabbb	H
abaaa	I/J	abaab	K	ababa	L	ababb	M
abbaa	N	abbab	O	abbba	P	abbbb	Q
baaaa	R	baaab	S	baaba	T	baabb	U/V
babaa	W	babab	X	babba	Y	babbb	Z

This code was invented by Sir Francis Bacon. The power of that code is that a's and b's in a message can easily be hidden: he allowed the a’s and b’s in his system to designate the different forms of anything that can be divided into two classes, sorts, or types (which Bacon referred to as the a-form and the b-form). Examples of a/b-forms are: colors of flower, size of objects,

Stream Cipher

Security Properties

• Stream cipher building block must be invertible, otherwise it is easy to create collisions.

Hash Functions

Security Attacks

• Man-in-the-Middle pre-image attacks.

Principle is to generate a message m = m₁||m₂, such that H(m)=h. If H(m)=g(F(IV,m₁),m₂), the MITM attacks consists in generate random m₁, m₂ until one get G^-1(h,m₂) = F(IV,m₁). Power of the attack relies on the fact that probability of finding a collision is inv. prop. to sqrt of the state size.

'Countermeasures' - prevent attacker to exploit symmmetry properties between round so that he can't discard part of the state, or control part of the state. Make attacker to use too much memory.

Fast hash (non-cryptographic)

• MEOW Hash (cryptanalysis)
• XXH3

See also HN comments on more functions

SHA2

SHA256

• Block size: 64 bytes (message chunk)
• State size: 128 bytes (64 for compression function + 64 for message schedule)
• 64 rounds

SHA512

• Block size: 128 bytes (message chunk)
• State size: 256 bytes (128 for compression function + 128 for message schedule)
• 80 rounds

Davis-Meyer

Davis-Meyer is a construcion that allows to build a hash function from a block cipher [8].

• H_{i} = E[In_{i}](H_{i-1}) XOR H_{i_1}

The input block are injected as the key, and the chaining value are chained as plaintext, and xor-ed into the output.

This construction is vulnerable to fixed-point (under some constraints), and hence gives weaker hash functions.

Custom Cryptographic Algorithms

This section is about variants of standard algorithms.

AES with secret S-boxes

Using AES with secret S-boxes may be interesting to protect against side-channel attacks as long as the S-boxes remain secret (and that adequate sharing on the linear part is in place).

References:

• The Retracing Boomerang Attack

Attack relevant for custom AES. Also state-of-the-art review on custom AES cryptanalysis.

Random Number Generator (rng)

More references:

• https://en.wikipedia.org/wiki/Lehmer_random_number_generator
• https://en.wikipedia.org/wiki/Lagged_Fibonacci_generator
• Improving QBasic RND generator (using Sponge4, a sponge over RC4)
• Randograms, visualize RNG.
• https://bytepawn.com/randomness-extractors-making-fair-coins-out-of-biased-coins.html

Linear Congruential Generator

Linear Congruential Generator (wikipedia) are easy to implement and provide good overall properties given the very low cost.

One the most known LCR are the one defined by Knuth

// https://en.wikipedia.org/wiki/Linear_congruential_generator
// https://stackoverflow.com/questions/23317439/integration-knuth-random-number-generator-to-my-code
// n = (n * 6364136223846793005 + 1442695040888963407) & 0xFFFFFFFFFFFFFFFF;
#define MY_RAND_MAX 0xffffffffffffffffLL

static
unsigned long long _myRandseed = 1;

// DO NOT TRUNCATE!
static
unsigned long long int (myrand)(void)
{
    _myRandseed = _myRandseed * 6364136223846793005 + 1442695040888963407;
    return((unsigned long long int) _myRandseed & MY_RAND_MAX);
}

✐	To truncate a LCG RNG, one must take the most significant bits, not the least significant.Linear Congruential Generator (wikipedia) Otherwise the RNG period is considerably reduced.

Linear Feedback Shift Register

Another easy way to produce RNG

Use simple hash function

In spinning-balls, one of Chrome’s benchmarks, we can see an example of this [9]:

// v8/benchmarks/spinning-balls/v.js

// To make the benchmark results predictable, we replace Math.random
// with a 100% deterministic alternative.
Math.random = (function () {
  var seed = 49734321
  return function () {
    // Robert Jenkins' 32 bit integer hash function.
    seed = seed & 0xffffffff
    seed = (seed + 0x7ed55d16 + (seed << 12)) & 0xffffffff
    seed = (seed ^ 0xc761c23c ^ (seed >>> 19)) & 0xffffffff
    seed = (seed + 0x165667b1 + (seed << 5)) & 0xffffffff
    seed = ((seed + 0xd3a2646c) ^ (seed << 9)) & 0xffffffff
    seed = (seed + 0xfd7046c5 + (seed << 3)) & 0xffffffff
    seed = (seed ^ 0xb55a4f09 ^ (seed >>> 16)) & 0xffffffff
    return (seed & 0xfffffff) / 0x10000000
  }
})()

Mersenne Twister

See https://en.wikipedia.org/wiki/Mersenne_Twister.

Combined

The idea is to take two or more simple RNG, and combine them (eg. by exclusive-OR).

PCG

• PCG stands for Permuted Congruential Generator.
• Reference: PCG, A Family of Better Random Number Generators
• Review [10], response [11]

// *Really* minimal PCG32 code / (c) 2014 M.E. O'Neill / pcg-random.org
// Licensed under Apache License 2.0 (NO WARRANTY, etc. see website)
// https://www.pcg-random.org/download.html

typedef struct { uint64_t state;  uint64_t inc; } pcg32_random_t;

uint32_t pcg32_random_r(pcg32_random_t* rng)
{
    uint64_t oldstate = rng->state;
    // Advance internal state
    rng->state = oldstate * 6364136223846793005ULL + (rng->inc|1);
    // Calculate output function (XSH RR), uses old state for max ILP
    uint32_t xorshifted = ((oldstate >> 18u) ^ oldstate) >> 27u;
    uint32_t rot = oldstate >> 59u;
    return (xorshifted >> rot) | (xorshifted << ((-rot) & 31));
}

• oorandom — a minimalistic pseudorandom number generator in Rust.

... also comes with a brief history of random numbers

Quasi-random sequence

• The Unreasonable Effectiveness of Quasirandom Sequences

An impressive study on how to generate random-looking sequence with better sampling properties than uniform distribution while less regular than lattice.

Low-discrepancy sequence

• Low-discrepancy sequences (wikipedia) are sequences that have a low discrepancy (wikipedia).
• Here some methods to generated low-discrepancy sequences: https://blog.demofox.org/2017/05/29/when-random-numbers-are-too-random-low-discrepancy-sequences/.
• Note that the uniform sequence (or N-dimension grid) does NOT have a low discrepancy: https://math.stackexchange.com/questions/2283671/is-it-expected-that-uniform-points-would-have-non-zero-discrepancy.

• One reason is that we can exploit the alignment of point to make the volume close to zero while encompassing sequence points, or to exploit empty gaps between points.
• For this reason, some definition of discrepancy only allow sub-intervals of the form [0,t[ instead of arbitrary ones [s,t[ (https://math.stackexchange.com/questions/1681562/how-to-calculate-discrepancy-of-a-sequence).

Useful algorithms

Fisher–Yates shuffle - Random permutation of a finite sequence

• https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 downto 1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]

Bloom filters

Bloom filters are very compact and efficient data structure that can tell whether an element is in a set with definitive no answer, or probable yes (with some predefined probability).

• https://scotthelme.co.uk/when-pwned-passwords-bloom/

Attacks

Rainbow tables

• See [12], [13].
• Goal is to reduce the cost of storing big pwd-hash tables.
• How:

• Use the hash function h=H(p), and a reduction function p=R(h).
• Build a chain p0 -> ... -> h_{n-1}, with intermediate p_i, h_i.
• To avoid loop, the reduction function at each step is different. So even if two hashes reduces to same pwd (and hence to same hash), next reduction will likely generate a different pwd.
• Build several chains of fixed length.
• Start searching in the chain backward.

• Best fix: use salt.

Side-channel

Tools

• MaskVerif — maskVerif is a tool that was first designed in 2015 to automatically and formally verify higher-order masking implementations. Operating on pseudo-code in SSA form, it returns either a security proof in some chosen leakage model, or a list of potential attacks.
• Rosita (GitHub) — Rosita is a code rewrite framework aims at eliminating side-channel leakage from masked implementations. It uses a leakage emulator (based on ELMO) to identify leaking instructions, and applies code modifications to eliminate the leakage.

• ROSITA: Towards Automatic Elimination of Power-Analysis Leakage in Ciphers (pdf)

Committing security

• Committing schemes prevent constructing a ciphertext that decrypts without error under more than one key.

AES-GCM

• AES-GCM takes a nonce N, message M, and key K to produce ciphertext C and tag T.
• One can easily find a collision: (C,T) = AES-GCM-Enc(Ka,Ma,Na) = AES-GCM-Enc(Kb,Mb,Nb).

• This also works for same nonce, ie N = Na = Nb.

• That is, for a same ciphertext-tag pair, the pair decrypts to different message under different key-nonce.

Weakness in GHASH:

• Nice algebraic properties.
• One can fix the last cipherblock using inverse. This can be used to generate 2 keys that decrypts same ciphertext.

• See https://eprint.iacr.org/2019/016.pdf (Fast Message Franking: From Invisible Salamanders to Encryptment)

• Can also produce multi-key-collision, ie. same ciphertext of length O(k) that decrypts under k different keys.

• See https://eprint.iacr.org/2020/1491.pdf Partitioning Oracle Attacks
• Can be used to accelerate password-recovery attacks.