Cryptography

Tomorrow\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\'s Cryptography:

Parallel Computation via Multiple Processors, Vector

Processing, and Multi-Cored Chips

Eric C. Seidel, advisor Joseph N. Gregg PhD

December 30, 2002

Abstract. This paper summarizes my research during my independent study on cryptography

in the fal l term of 2002. Here I state the growing need for better cryptography, introduce con-

sumer hardware architectures of near future, and identify the growing discrepancy between

the hardware on which current cryptographic standards were designed and the hardware the

future consumer wil l be using. I note then the need for a new \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\"modern\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\" cryptography based

on the presence of paral lel processing capabilities in forthcoming consumer machines and the

lack of support of such capabilities in some current and al l legacy crypto algorithms. I list

approaches used in past research to paral lelize cryptographic algorithms. I then summarize

various current algorithms and potential implementation changes to ready them for tomor-

row\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\'s machines. I conclude with some brief discussion of newer cryptographic algorithms,

particularly AES and AES finalists and how they wil l fare on the machines of the future.

Eric.C.Seidel@lawrence.edu; Joseph.N.Gregg@lawrence.edu

1

Contents

1 The future of crypto 3

2 Parallel crypto of to day 6

3 The imp ortance of data-level changes 8

4 Making data-level changes 9

4.1 Hashing Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

4.1.1 MD5 - Message Digest 5 . . . . . . . . . . . . . . . . . . . . . . . . . 13

4.1.2 SHA-1, Secure Hash Algorithm - Revision 1 . . . . . . . . . . . . . . 14

4.1.3 RIPEMD-160 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

4.1.4 Tiger . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

4.2 Block Cyphers (Secret Key Cryptography) . . . . . . . . . . . . . . . . . . . 17

4.2.1 DES - Data Encryption Standard . . . . . . . . . . . . . . . . . . . . 18

4.2.2 3DES - \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\"Tripple-Des\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\" .......................... 20

4.2.3 Serpent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

4.2.4 Twofish . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

4.2.5 Rijndael - the American Encryption Standard . . . . . . . . . . . . . 22

4.2.6 RC6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

4.3 Public-Key Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

4.3.1 RSA - Prime Factorization . . . . . . . . . . . . . . . . . . . . . . . . 26

5 Final Thoughts 27

2

1 The future of crypto

From bank accounts, to medical records, personal emails, and more, increasingly more and

more sensitive data is stored digitally. With the continued growth of the Internet, more

and more of this data resides in places which themselves may not be secure from intruders,

and much of this data is transferred

daily from place to place across connections inherently

insecure. To solve these problems of digital data security, we have cryptography. Most cryp-

tography however has historically been used by governments, larger business and computer

geeks and not by the average consumer. But, needs are shifting, and consumers are increas-

ingly using encrypted emails, encrypted