Cryptography

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

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

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

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++

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) ))

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.

Generate RSA Keys

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

sudo plainrsa-gen -b 2048 -e 3

# : PUB 0sAQOTQ2zIwqxqjy4LRTwXEHB/WdxMrrcldKBAut3siLnuQMCDFGkwSfOc9v+77ibPDqtJQj0C8nys7+W1gI3o6yht+SjG+m16hZwvwl0Mt81E11Tca6k6py1wNmntxvePtotG3uk6MhqpluJAUeOxIL6YcHLcsgBi19gwHiU1YBFF2Q==
: RSA   {
        # RSA 1024 bits
        # pubkey=0sAQOTQ2zIwqxqjy4LRTwXEHB/WdxMrrcldKBAut3siLnuQMCDFGkwSfOc9v+77ibPDqtJQj0C8nys7+W1gI3o6yht+SjG+m16hZwvwl0Mt81E11Tca6k6py1wNmntxvePtotG3uk6MhqpluJAUeOxIL6YcHLcsgBi19gwHiU1YBFF2Q==
        Modulus: 0x93436cc8c2ac6a8f2e0b453c1710707f59dc4caeb72574a040baddec88b9ee40c08314693049f39cf6ffbbee26cf0eab49423d02f27cacefe5b5808de8eb286df928c6fa6d7a859c2fc25d0cb7cd44d754dc6ba93aa72d703669edc6f78fb68b46dee93a321aa996e24051e3b120be987072dcb20062d7d8301e2535601145d9
        PublicExponent: 0x03
        PrivateExponent: 0x622cf33081c8470a1eb22e280f604aff913d88747a18f86ad5d1e9485b269ed5d5acb84620314d134f5527f419df5f1cdb817e01f6fdc89fee79005e9b4770484de1f0c003dcbeac2290f28f5594022ec0ca86fd0618ec77d0db3f24e0ddd9339a77b1126f3256d9405ce86bcd456f4db2ef0c019a763abee74eb29cb161568b
        Prime1: 0xc37626fcd807b365f62e70d07ad1c2383f0a987f373eca93bbd723bd6676062263fef48a1c99efbb4e2d64d82fecc1756ea3845db786746d9145f5c267931f5d
        Prime2: 0xc0dfb6dd8fa7b43405ba80653c9d7f58f4a208ae7a430028c149eb523fccea9b7b2c6b146eb53795b3879069cd4bd62e7568c651e12b0b4c43e22387ee6c24ad
        Exponent1: 0x824ec4a890052243f9744b35a736817ad4b1baff7a29dc627d3a17d399a40416ed54a306bdbbf527897398901ff32ba39f17ad93cfaef8490b83f92c450cbf93
        Exponent2: 0x80952493b51a7822ae7c5598d313aa3b4dc15b1efc2caac5d631478c2a889c67a772f20d9f237a63cd050af13387e41ef8f08436961cb232d7ec17aff4481873
        Coefficient: 0x80c5560ddad756e413c19fb39c83370dfa3ca5881ebb0b0a5098fbd81b007e20c7b7a104b0aada943d2f5ae64409a9e3b677e10d5c20f414959a621852424b19
  }

Another solution is to use openssl:

openssl genrsa 256 | openssl asn1parse

This gives:

Generating RSA private key, 256 bit long modulus
....+++++++++++++++++++++++++++
..........+++++++++++++++++++++++++++
e is 65537 (0x10001)
    0:d=0  hl=3 l= 171 cons: SEQUENCE          
    3:d=1  hl=2 l=   1 prim: INTEGER           :00
    6:d=1  hl=2 l=  33 prim: INTEGER           :BEF5D2D6550C4CF428A59A9099573D325D350F603E0C538B17CE6AFA7D2513B9
   41:d=1  hl=2 l=   3 prim: INTEGER           :010001
   46:d=1  hl=2 l=  32 prim: INTEGER           :316F66238264EACF126EBCB2CE5F9D41A74C7DE23069107B73CB664B505C0BD9
   80:d=1  hl=2 l=  17 prim: INTEGER           :F83F3AAC16EA5DFDCF8F08C85415EEA3
   99:d=1  hl=2 l=  17 prim: INTEGER           :C4EC941CCE450AF0B6ED7AA8D73225F3
  118:d=1  hl=2 l=  17 prim: INTEGER           :ECCFB472B1B185543809E480E5E5BE2D
  137:d=1  hl=2 l=  17 prim: INTEGER           :8CF9A4AADE8C14E1F0C31FEDA169383B
  156:d=1  hl=2 l=  16 prim: INTEGER           :1E8BD8FD9E1B1FC747B2C269ECA6CAA5

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

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

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

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.