Overview of DES & RSA Encryption Algorithms: Overview of DES & RSA Encryption Algorithms Shawn Hillis 16 April 2002 CGS 5132 Computer Forensics 2
Overview of DES: Overview of DES 16 cycles of combinations: Substitution technique (for confusion) Transposition technique (for diffusion) plaintext initial phase left right function F inverse initial phase ciphertext 16x
DES Overview (cont): DES Overview (cont) Plaintext encrypted in blocks of 64 bits Keys are 64 bits long (only 56 are really needed) Standard arithmetic/logical operations - very fast Four Modes of Operation ECB - Electronic Code Book CBC - Cipher Block Chaining OFB - Output Feedback CFB - Cipher Feedback
DES S-Boxes: DES S-Boxes Critical component of DES Known (public) implementation standard but design specs and requirements still classified Some believe requirements and specs contain a “back door” No such weakness yet found by analysis Non-linear bit shifting and bit substitutions avoids frequency analysis attacks and greatly weakens differential cryptanalysis attacks as well
DES S-Boxes (cont): DES S-Boxes (cont) “Avalanche criteria” condition where every single bit of the ciphertext depends on every bit of both the cleartext and the key DES reaches the avalanche criteria by the 5th round Triple DES (3-DES) - simply DES performed three times with three different keys extends key to ~(56 x 3) bits
Generic RSA Algorithm: Generic RSA Algorithm Select two large primes (p & q) at random (~100 digit) heuristic algorithms to decide primality Compute their system modulus: N=p q Select encryption key e, where e<N and gcd(e, (N))=1 (N) number of integers {1 - (N-1)} that are relatively prime to N (I.e. gcd(I,N) = 1) (N) = (p-1)(q-1) Euler’s formula: if gcd(a,m) = 1, then a (m) = 1 (mod m)
Generic RSA Algorithm (cont): Generic RSA Algorithm (cont) Solve for decryption key d : e d = 1 mod (N) and 0 d N d = inverse e mod (N) (e.g. 9 = inverse 3 mod 26) Public key = {e,n} Private key = {d, p, q} Protection = difficulty in calculating (N) Plaintext value = x Ciphertext value = y = x^e mod N Decryption key d = inverse e mod (N) Inverses: x & y such that x * y = 1 Ex: 3 = inverse 7 mod 20 -- 3 * 7 = 21, 21 mod 20 = 1
RSA Simple Example: RSA Simple Example Pick p = 3, q = 7 N = p * q = 21, (N) = (p-1)(q-1) = 12 Pick e = 5 ( 5 < 21, gcd(5,12) = 1) Public keys = {5,21} Private keys = {3,7} or {12} Decryption key d = 5 --- 5 * 5 mod 12 = 1 Encryption of x = 11 (y = x^e mod N) y = 11^5 mod 21 y = (161051) mod 21 y = 2 -- 161051/21 = 7669 r 2 Decryption of y = 2 (x = y^ d mod N) x = 2^5 mod 21 x = 32 mod 21 x = 11
References: References RSA Laboratories, “Frequently Asked Questions About Today's Cryptography”,Version 4.1, May 2000, http://www.rsalabs.com/faq/index.html Lawrie Brown, “Cryptography and Computer Security - Lectures”, Australian Defense Force Academy, http://www.cs.adfa.oz.au/teaching/studinfo/csc/lectures/ Computer Security Resource Center, National Institute of Standard and Technology, http://csrc.nist.gov/ FAQ.org, “Cryptography FAQ”, http://www.faqs.org/faqs/cryptography-faq/, Nov 2001
References (cont): References (cont) Daniel D. Houser, “Digital Encryption Standard: A New Look at the DES Lifecycle”, SANS Institute, http://www.sans.org/infosecFAQ/encryption/DES.htm, April 2001 Douglas R. Stinson, “Cryptography, Theory and Practice”, Univ. of Nebraska, CRS Press, 1995