Cryptography: Difference between revisions
Line 572: | Line 572: | ||
* '''Affine coordinates''' — The standard <code>(x,y)</code> coordinates used in curve's equation. These coordinates must be completed with the ''point-at-infinity'', which has no affine representation. |
* '''Affine coordinates''' — The standard <code>(x,y)</code> coordinates used in curve's equation. These coordinates must be completed with the ''point-at-infinity'', which has no affine representation. |
||
* '''Projective coordinates''' — Triplet <code>(x,y,z)</code>. Given affine coordinate <code>(X,Y)</code>, we have <code>X=x/z; Y=y/z</code>. Point at infinity has coordinate <code>(0,y,0)</code>, ie <code>z=0</code>. Using projective coordinates same modular inverse operation (dividing by z). |
* '''Projective coordinates''' — Triplet <code>(x,y,z)</code>. Given affine coordinate <code>(X,Y)</code>, we have <code>X=x/z; Y=y/z</code>. Point at infinity has coordinate <code>(0,y,0)</code>, ie <code>z=0</code>. 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 |
|||
== Quantum Cryptography == |
== Quantum Cryptography == |
Revision as of 10:49, 30 October 2019
References
Key Lengths
RSA
See recommendations from Bruce Schneier in Applied Cryptography (§7.2, [1]). See also [2]
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
|
|
|
|
- More bench
- (see SharkSSL_Benchmark_for_ARM_Cortex_M3.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:
- Reading these tests is the best way to understand how to use the library.
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.
- 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
# 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:
- Specifies the recommended curves for ECC (NIST Curve P-256, Curve P-384...).
- 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
- 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 haveX=x/z; Y=y/z
. Point at infinity has coordinate(0,y,0)
, iez=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
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
- Classical Homomorphic Encryption for Quantum Circuits
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:
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 = m1||m2, such that H(m)=h. If H(m)=g(F(IV,m1),m2), the MITM attacks consists in generate random m1, m2 until one get G-1(h,m2) = F(IV,m1). 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.
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:
- Attack relevant for custom AES. Also state-of-the-art review on custom AES cryptanalysis.