### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# CryptographyComp Netwk Sec ECE 646

Mason

GPA 3.94

### View Full Document

## 248

## 0

## Popular in Course

## Popular in ELECTRICAL AND COMPUTER ENGINEERING

This 176 page Class Notes was uploaded by Antonina Wuckert on Monday September 28, 2015. The Class Notes belongs to ECE 646 at George Mason University taught by Krzysztof Gaj in Fall. Since its upload, it has received 248 views. For similar materials see /class/215023/ece-646-george-mason-university in ELECTRICAL AND COMPUTER ENGINEERING at George Mason University.

## Reviews for CryptographyComp Netwk Sec

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/28/15

ECE 646 Lecture 15 Cryptographic standards Secretkey cryptography standards Federal Banking International standards standards standards NIST ANSI ISO FIPS 46 1 DES X392 DES FIPS 46 2 DES ISO 8732 Modes of operation FIPS 81 Modes of X3106 DES modes of operation 9 644 operation clpher X952 Modes of operation ISO 10116 Modes of FIPS 463 Triple ofTriple DES Operation of an n bit FIPS 197 AES cipher NIST FIPS National Institute of Standards and Technology Federal Information Processing Standards American Federal Standards Required in the government institutions Original algorithms developed in cooperation with the National Security Agency NSA PublicKey Cryptography Standards unof cial industry mdu my standards standards RSA Labs IEEE PKCS PKCS P1363 international bank standards standards 1 ISO ANSI ISO ANSI X9 federal standards NIST FIPS PKCS PublicKey Cryptography Standards Informal Industry Standards developed by RSA Laboratories in cooperation with Apple Digital Lotus Microsoft MIT Northern Telecom Novell Sun First except PGP formal specification of RSA and formats of messages IEEE P1363 Working group of IEEE including representatives of major cryptographic companies and university centers from USA Canada and other countries Part of the Microprocessors Standards Committee Modern open style Quarterly meetings multiple teleconferences discussion list very informative web page with the draft versions of standards IEEE P1363 Combined standard including the majority of modern public key cryptography Several algorithms for implementation of the same function Tool for constructing other more specific standards Specific applications or implementations may determine a profile subset of the standard ANSI X9 American National Standards Institute Work in the subcommittee X9F developing standards for financial institutions Standards for the wholesale e g interbank and retail transactions np bank machines smart card readers ANSI represents USA in ISO ISO International Organization for Standardization International standards Common standards with IEC International Electrotechnical Commission ISOIEC JTCl SC 27 Joint Technical Committee 1 Subcommitte 27 Full members 21 Australia Belgium Brazil Canada China Denmark Finland France Germany Italy Japan K0rea Holland Norway Poland Russia Spain Sweden Switzerland UK USA ISO International Organization for Standardization Long and laborious process of the standard development Study period NP New Proposal Minimum WD Working Draft 3 years CD Committee Draft DIS Draft International Standard IS International Standard Review of the standard after 5 years ratification corrections or revocation Publickey Cryptography Standards international I bank standards dno iclal industry standards ISO mdu my standards standards ANSI ISO RSA Labs IEEE PK ANSI X9 PKCS P1363 federal standards NIST FIPS 1991 1992 1993 1994 1995 1996 199719981999 PKCS PKCS 1 10 meg 711PKCs 13 5 e e i e PKCfs 1 v20 IEEE P136321 3 365 ANSI X930DSA magic 2 SA 6 X951 R A RW ISO 9796 101151 11770 3 DH e e m X 10118 3 14888ESA w FIPS 1801 939 964NR NIST FIPs 180 SHA e e e SHA39I a FIPS 136DSS I IPS1861DSAampRSA IEEE P1363 discrete logarithm elliptic curve discrete logarithm RSA wnh OAEP RSA amp R W DSA EC DSA 3 w1th ISO14888 NR with ISO 9796 EC NR or ISO 9796 w1th ISO 9796 EC DHl Md EC DH2 DH2 an MQV and EGMQV IEEE P136321 RSA with OAEP discrete logarithm new scheme elliptic curve discrete logarithm new scheme W 180399796 NR with ISO9796 EC NR or with ISO 9796 EC DHl DH1 new scheme DH2 amp MQV EC DH2 amp ECMQV ANSI X9 Standards logarithm elliptic curve discrete Industry standards PKCS discrete f t t ac onza 10 loga t elliptic curve discrete logarithm PKCS 1 PKCS 13 RS A new scheme PKCS 13 RSA i R EC DSA key PKCS 2 PKCS 13 agreement DH EC39DHI 2 ECMQV NIST FIPS 39 discrete elliptic curve factorizatlo logarithm discrete logarithm FIPS 1861 FIPS 186 FIPS 1862 RSA DSA EC DSA key agreement International standards ISO 39 discrete elliptic curve facmmatm logarithm discrete logarithm ISO 97961 ISO148883 ISO148883 ISO 97962 ISO 97964 ISO 97964 ISO117703 ISO117703 Secure key sizes discrete elliptic curve discrete PKCS IEEE P1363 ANSI X9 2 1024 NIST FIPS 512 s Ls1024 ISO Padding schemes signatures h with message recovery OAEP PKCS 1 PKCS PKCS 1 IEEE F1363 OAEP ISO 14888 ISO 9796 ANSI X9 OAEP ISO 14888 ISO 9796 NIST FIPS 1S0 ISO 14888 ISO 9796 Hash functions based based on dedicated 011 bIOCk modular Ciphers arithmetic MDS PKCS Mm SHAl IEEE P1363 RIPEMD160 SHAl ANSI X9 RIPEMD160 SHAl SHA256 NIST FIPS SHA384 SHA512 ISO SHAl MDGZ MASH1 RIPEMD128 160 MASH2 Notes for users of cryptographic products 1 Agreement with a standard does not guarantee the security of a cryptographic product Security secure algorithms guaranteed by standards 0 proper choice of parameters secure implementation proper use ECE 646 Lecture 6 Towards modern ciphers SP networks amp DES Onetime Pad Vernam Cipher Gilbert Vernam ATampT 1926 A tyoersephAlauborgne 01211116319 mi OlllOllOlOlOOlOlOllOlOl k llOlllOlllOllOlOlllOllO 1 Ci lOlOlOllOllllllllOOOOll All bits of the key must be chosen at random and never reused Onetime Pad Equivalent version cimikimod26 Hg TO BE OR NOT TO BE k AX TC VI URD WM OF 1 0 TL UG JZ HFW PK PJ 1 All letters of the key must be chosen at random and never reused Perfect Cipher Claude Shannon Communication Theory of Secrecy Systems I 948 V PMm CcPMm meM 06C The cryptanalyst can guess a message with the same probability without knowing a ciphertext as with the knowledge of the ciphertext Is substitution cipher a perfect cipher C XRZ PMADD 0022 0 PMADD 72 0 Is onetime pad a perfect cipher C XRZ PMADD CXRZ 7t 0 PMADD 7t 0 M might be equal to CAT PET SET ADD BBC AAA HOT HIS HER BET WAS NOW etc SP Networks 3 3 33 Basic operations of SP networks Substitution Permutation oi n u ooo IIII Oi D ID IOD ID I Ot t It IOOO Ot OOD iD IO Sbox Pbox Avalanche effect c gt c7 c2gt c2 C gt 4 gt Cs cs s H a s 4 c6 7 gt gt 91 439 2 gtT8 w m 3m 4 mm 4 mu 4 m2 4 m m 3 Mi amp a amp Mi Mi amp Horst F eistel Walt T uchman LUCIFER BM km km kms quot 1 4p 4 4D 91 quot 2 4p 4p 4b g 4 4 4 c3 m4 4 4 4 M M w 33 k31 K3 2 P k3 16 m m9 4h 4b 4p 4 m 4h 4b 4p 4 4 Cm mu 4 4 4p 4 Cu quot 12 4h 4b 4p 4 c2 k3Z1 k3ZZ 3216 quot 12 4 4 4p 4 125 m26 4 4p 4p 4 9125 m27 4 4D H 4 c127 mIZX I I 16 rounds LUCIFER external 100k plaintext block 128 bits 512 bits 128 bits ciphertext block NBS public request for a standard cryptographic algorithm May 15 1973 August 27 1974 The algorithm must be 0 secure public completely speci ed easy to understand available to all users economic and efficient in hardware able to be validated exportable DES chronicle of events 1973 NBS issues a public request for proposals for a standard cryptographic algorithm 1975 rst publication of the IBM s algorithm and request for comments 1976 NBS organizes two workshops to evaluate the algorithm 1977 of cial publication as FIPS PUB 46 Data Encryption Standard 1983 1987 1993 recerti cation of the algorithm for another ve years 1993 software implementations allowed to be validated Controversies surrounding DES Unknown Slow Too short design in software key criteria Most criteria h Odnly I reconstructed lar WE Theoretlcal from cipher Imp emen Ions dCSIgns analySis cemfled of DES breaking machines 1990 39 39 1993 1998 RemVemlOn Software rmware P t 1 of differential and hardware rac 10a DES cracker ClyptanaIYSiS treated equally built Life of DES 1970 1980 1990 2000 Time DES developed by tranSiSion IBM and NS A to a new standard In common use for over 20 years Federal and banking standard Over 130 validated implementations De facto worldwide standard Most popular secretkey ciphers 1980 1990 2000 2010 2020 2030 1977 19991 1 DES l Triple DES l American 56 bit key AES Rijndael standards AES 2001 128 192 and 256 bit ke ys 112 168bitkeys contest IDEA Serpent Other 1 popular RC5 Twofish algoritth Blowfish RC6 CAST Mars DES external 100k DES key 56 bits I 64 bits DES Main Loop Feistel Structure Ln1Rn Rn1Ln fRn Kym Feistel Structure Encryption Decryption Feistel Structure Encryption Decryption 10 General design criteria of DES 1 Randomness 2 Avalanche property changing a single bit at the input changes on average half of the bits at the output 3 Completeness property every output bit is a complex function of all input bits and not just a subset of input bits 4 Nonlinearity encryption function is nonaf ne for any value of the key 5 Correlation immunity output bits are statistically independent of any subset of input bits 11 Completeness property Every output bit is a complex function of all input bits and not just a subset of input bits Formal requirement For all values ofi andj i164jl64 there exist inputs X1 and X2 such that X1 X1X2X3Xi10Xi1X63X64 X2 X1X2X3Xi11Xi1X63X64 Y1 DESX1 Y1 Y2 Y3 Yj1 Yj Yj1 Y63 Y64 Y2 DESX2 Y1 Y2 Y3 Yj1 Yj Yj1 363 364 Linear Transformations Transformations that ful ll the condition TXmxl Ynxl Anxm 39 Xmx 1 Of TX1 93 X2 T041 lt9 TX2 Affine Transformations Transformations that ful ll the condition Tmx 1 Ynx l Anxm 39 Xmx 1 EB Bnx l 12 ECE 646 Cryptography an Computer Network Security Course web page ECE web page gt Courses gt Course web pages ECE 646 Kris Gaj at GMU since Fall 1998 Research and teaching interests I cryptography I network security I computer arithmetic I VLSI design and testing Contact Science amp Technology 11 room 223 kgajgmuedu 703 9931575 Of ce hours Monday Wednesday 730830 PM ECE 646 Part of MS in CpE Network and System Security required Computer Networks elective MS in EE Communications amp Networks elective Computers MS in Information Security amp Assurance MS in ECommerce Certificate in Information Systems Security PhD in Information Technology Fall 2005 as ofAugust 28 ECE 646 Options required for I MS in CpE I PhD in IT ECE 646 Lecmre Laboratory Project Homework 10 0 0 25 0 35 A Midterm exams Specz canun 7 5 20in class 5 42 10 0 10 A take home Wmer 72pm 7 8 ECE 646 Exam track LeCture Laboratory Final Project exam review Homework 10 3O 5 0 35 A in class Midterm exam 20 in class ECE 646 Options Target distribution Project track Exam 30k S 30 students projects breadth Lecture I viewgraphs Whiteboard I viewgraphs available on the Web please extend With your notes I books 1 required Stallings 2 optional available on reserve in the Johnson Center I anicles CryptoBytes RSA Data Security Con CHES CRYPTO etc I Web sites Crypto Resources standards FAQs surveys Homework 1 I reading assignments I theoretical problems may require basics of number theory or probability theory I problems from the main textbook I short programs I literature surveys Homework 2 I optional assignments short programs vs analytical problems or HDL codes More time consuming Typically less Most time spent time consuming on debugging More thinking Relatively stmightforward Lime writing Midterm exam 1 2 hours 30 minutes multiple choice test short problems openbooks opennotes practice exams available on the Web midterm exam review session optional Tentative date Monday October 31 st Midterm Exam 2 project track only takehome 24 hours literature search analytical problems submission through WebCT Tentative date Saturday December 1 0 Final exam ex am track only 2 hours 45 minutes Multiple choice several problems Monday December 12 730 7 1015 PM Laboratory I 45 labs I based on the GMU educational so ware public domain cryptographic programs amp libraries or evaluation versions of commercial products I done at home or in the ECE labs so ware downloaded from the web I based on detailed instructions I grading based on written reports answers to questions included in the instructions Tentative list of laboratory topics 1 Secure email PGP 7 Pretty Good Privacy Historical ciphers CrypTool Properties of classical cryptosystems Kryptos Properties of public key cryptosystems Kryptos Secure email SMlME exam track only ywa Project 1 I original I useful I depth originality I based on additional literature I you can start at the point where former students ended I based on something you know and are interested in I so ware hardware analytical I may involve experiments I teams of 14 students I several project topics proposed by the instructor I you can propose your own topic Project 2 I about four weeks to choose a topic and write the corresponding speci cation I regular meetings with the instructor I four oral progress reports based on Power Point slides I dra nal presentation due at the last progress report MondayTuesday December 56 I written reportarticle lSpage EEE style due Monday December 12 I short conferencestyle oral presentations Monday December 19 5001000 PM I contest for the best presentation I publication of reports and viewgraphs on the web Project 3 I Project reportsarticles requirements EEE style 15 pages maximum appendices possible but do not in uence the evaluation source codes made available to the instructor I Review of proj ect reports reviews done by your fellow students reviews due Friday December 16 800 PM nal version of the report due Monday December 19 500 PM Project 4 I Project presentations Monday December 19 5001000 PM conference style Johnson Center several sessions refreshments attendance in at least three sessions required open to general public in particular students from previous years ECE seminar credit 10 minutes for the presentation 5 minutes for QampA time strictly enforced Project Types Software Hardware program in a highlevel behavioral mode1 language C CH Jaw m HDL VHDL Verilog or assembly language mapped into FPGA or ASIC Hybrid SWHW Analytical comparative analysis HLL L W ofcompeting algorithms for arecon guarble protocols or implementation computer options survey ofthe market HVJPORTAN T RULE MS CpE Students lVl39UST choose implementation oriented projects ie Software Hardware or Hybrid SWHW Follow up courses Cryptography and Computer Network Security ECE 646 Secure Telecommunication computer Arithme c ECE 645 Systems ECE 746 Cryptography and Computer Secure Network Security Telecommunication Systems Modular integer arithrnetic Operations in the Galois Fields GF2 Histon39cal ciphers 39 classical encryptl Stream ciphers on DES IDEA RC5 AES Elliptic curve cryptosystems Public key encryption 39 cumu RSA DH DSA 39 8m cards Hash functions and MACs Digital signatures public key certi cates timing power analysis Ef cient and secure c Secure Internet Protocols Hm P61 and SMME Security in various kinds of n networ PSec wireless Zeroknowledge identi cation schemes www SSL Cryptographic standards Typical course diniculty This course dif culty Project topics Software Educational software for a cryptographic laboratory Prerequisites cct Idea Develop extensions to the existing GMU educational so mre or teaching cryptography KRYPTOS Examples oftasks provide a choice ofan underlying library currently only Cryp o faster libraries available but more di icult to integrate Examples OpenSSL MIRACL etc input editor sc hex Comparative Analysis of Software Multiprecision Arithmetic Libraries for Public Key Cryptography High GMPNTL LiDIA CLN w D E 3 OpenSSL g MIRACL O N 777177777quot 39 PIOLOGIE Ash raf AbuSharekh Low CryptoPP MS Thesis April 2004 LOW High Primitives Schemes Support Project topics Software Factoring of large numbers using Number Field Sieve Prerequisites CC Assumptions based on a multiprecision arithmetic library optimized for maximum speed timing measurements for various number sizes Project topics Software Analysis of capabilities and performance of Java Cryptography Extension JCE Prerequisites Java Assumptions scope of the library analysis of performance comparison with CC and ASM implementations practical applications of the library 10 rrojeu lupus Hardware Implementation of a selected secretakey cipher Implementation of a selected publicakey system eg NTRU using FPGA devices Prerequisites VHIDL or Verilog FPGA or semicustom ASIC design Assumptions design in ahardvmre descn39ption language at the RTL level 39 seemin am veri cation using available tool logic synthesis to the gatestandard cell level static timing analysis and timing simulation rrojeu lupus Hardware Implementation of a selected new mode of operation of a secretakey cipher providing both encryption and authentication eg OCB EAX CCM Prerequisites VHIDL orVerilog FPGA or semicustom ASIC design Assumptions design in ahardvmre descn39ption language at the RTL level optimization formaxlmum speed m39 39 area orminimum power veri cation using available tools logic synthesis to the gatestandard cell level static timing analysis and timing simulation rrojeu lupus Hardware Fully parallelizable hashing scheme with SL72 New hash functions suitable for hardvmre proposed at Crypto 1994 No serious implementations so ar Prerequisites VHIDL orVen39log FPGA or semicustom ASIC design Assumptions design in ahardvmre descn39ption language at the RTL level s ma veri cation using available tools logic synthesis to the gatestandard cell level static timing analysis and timing simulation compare vs microprocessor implementation What is a reconfigurable computer Reconfigurable processor Microprocessor system system mm 311me V0 Interface Interface V0 SRC 6E System httpwwwsrccompcom s aaaa e sRcMA1gtLDo4 SRC MAPTM Reconfigurable Processor 1400 MBIs 1400 MBls sustained sustained payload payload Microcode 39 Con g 4900 MBls Rmquot 6 X 64b Dualported Uri Board Memory 24 MB 500 MBIs 4WD MEI 6 x 54b 6 3 64b 4330 MBIS User Logic 1 1 User Logic 2 XCZVSOW Chain Ports MBls s nnnn e sRc MAPLD04 12 SRC HiBarTM Based Systems HiBar sustains 14 GBs per pon Up to 256 input and 256 output pons Common Memory CM has controller with DMA capability Up to 8 GB DDR SDRAM supported per CM no e SRC quotin 9mm m e no Inml SRC Programming HDL HLL VHDL C P system SRC 5 FPGA system Libra w Application Developer Programmer SRC Compilation Process Application sources Macro sources Con guration Applican39on bitstreans executable Run Time Reconfiguration in SRC Program in C or Fortran FPGA contents after the Function1 call M am program Function1 FPGA f1 Macro1a b c Function1 a d e Macro2b d Macro2c e Function2 Macro3s t Function2d e f 1n b Macro4tyk Project topics Hybrid SoftwareHardware Implementation of a selected secret key cipher RC5 IDEA DES using recon gurable computer Prerequisites programming in c basic understanding ofhardvmre Assumptions analysis ofavailahle literature high level design specification ofbasic compone design ofbasic components and functional veri cation timing analysis t the entire system Factoring oflarge numbers using Prerequisites prog of Assumptions analysis ofavailahle literature high level design specification ofbasic components design ofbasic components and the entire system functional verification timing anal 39 Project topics Hybrid SoftwareHardware t r ramming in c number theory basic understanding hardvmre knowledge ofVHDL helpful ysls Projects HardwareAnalytical Elementary Operations used in Modern Secret Key Ciphers analysis ofwrious algorithms from the point ofview ofhardware implementations comprehensive library ofbasic cryptographic primitives Projects HardwareAnalytical Survey of Cryptographic Chips and IP cores Survey of commercially available integrated circuim implementing cryptographic algorithms Survey of commercially available FPGA IP cores implementing cryptographic algorithms Partial list of encryption chipmakers Broadcom AEP Systems HiFn Corrent Cavium Motorola SafeNet Layer N Networks Intel NetContinuum NetOctave Philips Semiconductors Selected ASIC Security Chips a Chip name Encryptio HMAC Data rate Public key Other 1 algorithms Mbps algorithms algorithms Broadcom DESCBC SHAl 500 DH Onchip RNG BCM5823 3DES MD5 RSA CBC AESCBC AESCTR Broadcom 3DES SHAl 4800 none Inline IPsec BCM5841 CBC MD5 processing AESCBC Onchip SA database AESCTR RNG Selected ASIC Security Chips Chip name Encryptio HMAC Data rate Public key Other 11 algorithms Mbps algorithms Nitrox Lite alg gms SHAl 1000 DH Inline IPsec CN1010 3DES MD5 RSA processing AES RSA 7K 1024 ARC4 RSA39ssec 0n chi RNG NITROX II DES SHAl 10000 DH Inline Psec CN2560 3DES MD5 RSA ProceSSing AES RSA 40K 1024 ARC4 RSA39ssec On chip RNG 2M SA39s with 512 MB DRAM Adapts to quothankquot Innll Families of Cavium chips Nitrox Lite Nitrox Nitrox l6 Projects Analytical Cryptographic capabilities of Network Processors Example Intel IXP2850 Projects Analytical Key management Survey of so ware packages supporting Public Key Infrastructure Report on commercial Certification Authorities Projects Analytical Security Protocols 0 Secure WWW servers Security options in the W W W browsers 0 Secure protocols for wireless ad hoc networks ECE 646 Cryptography and Computer Network Security Course web page httpecegrnueducoursesECE543 ECE web page gt Courses gt Course web pages gt ECE 646 Kris Gaj Assistant Professor at GMU since Fall 1998 Research and teaching interests cryptography network security computer arithmetic VLSI design and testing Contact Science amp Technology 11 room 223 kgajgmuedu 703 9931575 Of ce hours T R 430530 PM W 730830 PM ECE 646 Part of MS in CpE Network and System Security Computer Networks MS in EE Communications Computer Engineering MS in ECommerce Certificate in Information Systems Security Network and System Security I ECE 542 I I lNFS 762 Project track ECE 646 Options Exam track ECE 646 Project track Lecture J Laboratory Project Homework 10 35 25 Midterm exams Speci cation 5 0 Results 12 20 0A In Class Oral presentation 10 10 A take home Written report 8 ECE 646 Lecture Laboratory Homework 35 Midterm exam 20 in class 10 Final Project exam review 30 5 in class ECE 646 Options Target distribution Project track Exam track 5 12 project teams 2 12 students Lecture viewgraphs chalk amp blackboard viewgraphs available on the web please extend with your notes books 1 required Stallings 2 optional available on reserve in the Johnson Center articles CryptoBytes RSA Data Security Conf CHES CRYPTO etc web sites Crypto Resources standards FAQs surveys Homework 1 reading assignments theoretical problems may require basics of number theory or probability theory problems from the main textbook short programs literature surveys Homework 2 optional assignments short programs vs analytical problems or HDL codes V More time consuming Typically less V Most time spent time consuming on debugging More thinking V Relatively straightforward Little writing Midterm exam 1 Both tracks V 1 hour 30 minutes V multiple choice test 3 problems V practice exams available on the web V midterm exam review sessions optional Tentative date October 29 Final exam Exam track only V 2 hours 45 minutes V multiple choice test 6 problems Wednesday December 10 430 715 PM Project 1 depth originality based on additional literature you can start in the point where former students ended based on something you know and are interested in software hardware analytical over 30 project topicsdescriptions available on the web teams of 15 students may involve experiments you may propose your own topic Project 2 about four weeks to choose a topic and write the specification regular meetings with the instructor four oral progress reports based on Power Point slides draft final presentation due at the last progress report Wednesday December 3 written reporUaIticle lSpage IEEE style due Saturday December 6 short conferencestyle oral presentations Friday December 12 500900 PM contest for the best presentation publication of reports and viewgraphs on the web Project 3 Project reportsarticles requirements IEEE style 15 pages maximum appendices possible but do not in uence the evaluation source codes made available to the instructor Review of project reports reviews done by students from the exam track reviews due Tuesday December 9 midnight final version of the report due Friday December 12 500 PM Project 4 Project presentations Friday December 12 500900 PM conference style Johnson Center 4 sessions refreshments students from both tracks required to attend open to general public in particular students from previous years ECE seminar credit 10 minutes for the presentation 5 minutes for QampA time strictly enforced Review of project presentations draft presentations in Power Point due Wednesday December 3 review by the instructor Project Types Software program in a highlevel language C C Java or assembly language SoftwareHardware program for a recon guarble computer or FPGA accelerator board Hardware behavioral model in HDL VHDL Verilog mapped into FPGA or ASIC veri ed using timing simulation Analytical comparative analysis of competing algorithms protocols or implementation options survey of the market Laboratory 34 labs based on the GMU educational software public domain cryptographic programs amp libraries or evaluation versions of commercial products done at home or in the ECE labs software downloaded from the web based on detailed instructions grading based on written reports answers to questions included in the instructions Tentative list of laboratory topics 1 Properties of classical cryptosystems 2 Properties of public key cryptosystems 3 Properties of hash functions 4 Secure email Pretty Good Privacy and SMIIVIE Followup courses Cryptography and Computer Network Security ECE 646 Secure Telecommunication computer Anthmetlc ECE 645 Systems ECE 746 Cryptography and Computer Secure Network Security Modular integer arithmetic Telecommunication Systems Operations in the Galois Fields GF2 Historical ciphers Classical encryption DES IDEA RC5 AES Public key encryption RSA DH DSA Hash functions and MACs Digital signatures Public key certi cates Secure Internet Protocols email PGP and SMIME www SSL Cryptographic standards AES Stream ciphers Elliptic curve cryptosystems Random number generators Smart cards Attacks against implementations timing power analysis Ef cient and secure implementations of cryptography Security in various kinds of networks IPSec wireless Zeroknowledge identi cation schemes Typical course dif culty time dif culty This course We Important Announcement ll Due to the instructor s attendance in two conferences in Europe FPL and CHES Class 2 Security Services Basic Concepts of Cryptology is moved from Wednesday September 3 430710 PM to Sunday September 14 1100200 PM Class 3 Historical Ciphers Enigna is moved from Wednesday September 10 430710 PM to Saturday September 20 1100200 PM Project topics Software SEl Educational software for a cryptographic laboratory Prerequisites CC GUI development under Windows Team 35 students Assumptions based on public domain libraries and web search extended Visualization and editing secret parameters partial results ASCII hex binary choice of arbitrary parameters modes and key sizes weak keys timing measurements statistical tests Project topics Software SAl Survey of libraries of operations on large integers and elements of the Galois eld Prerequisites CC Java Windows Unix Linux Team 35 students Assumptions public domain libraries supported arithmetic operations portability analysis of performance on various platforms explanation of performance differences analysis of the source codes and documentation algorithms used to implement arithmetic operations ease of use documentation and support Project topics Software SAZ Comparative survey of selected public domain cryptographic libraries Prerequisites CC Java Windows Unix or Linux Team 35 students Assumptions source codes available in public domain supported cryptographic algorithms classical 3DES AES RC5 IDEA etc public key RSA ECC DH DSA NTRU portability analysis of performance on various platforms explanation of performance differences analysis of the source codes and documentation ease of use documentation and support Project topics Software Generating large primes for cryptographic applications Prerequisites CC Team 15 students Assumptions analysis of several available algorithms choice of the library implementation of selected algorithms timing measurements for various prime sizes comparative analysis Project topics Software SA3 Analysis of the public domain software implementations of IPSec Prerequisites CC FreeB SD Unix or Linux administrator level Team 35 students Assumptions public domain implementations of IPSec such as FreeSW AN public domain implementation of the Internet Key Exchange such as Pluto experimental veri cation speed penalty measurement interface to the hardware accelerators comparative analysis of performance ease of use documentation and support Project topics Software SPC2 Factoring large integers using distributed computing resources Prerequisites number theory CC distributed computing basics Linux Team 35 students Assumptions use of one of the available Job Management Systems CODINE Condor PBS adjusting the public domain software for factoring of large numbers experimental analysis minimizing the effect on local users fault tolerance issues attack on a medium size number Project topics Hardware HCI l Implementation of a selected secretkey cipher IIPI3 Implementation of a selected publickey system eg NTRU using FPGA devices Prerequisites VHDL or Verilog FPGA or semicustom ASIC design Team 35 students Assumptions design in a hardware description language at the RTL level optimization for maximum speed or minimum area veri cation using available tools logic synthesis to the gate standard cell level static timing analysis and timing simulation possible experimental testing using the SLAAC lV or Wild Star 11 FPGA boards Project topics Hardware HCI 3 Porting NSA VHDL codes for AES candidates to Field Programmable Gate Arrays Prerequisites VHDL FPGA design Team 23 students Assumptions starting from the NSA VHDL codes available in public domain adjusting the codes so they compile using available FPGA tools functional veri cation using test vectors logic synthesis mapping placing and routing static timing analysis and timing simulation possible experimental testing using the SLAAC lV 0r Wild Star 11 FPGA board Project topics SoftwareHardware Factoring of large numbers using recon gurable computer Prerequisites programming in C number theory basic understanding of hardware Team 35 students Assumptions analysis of available literature including papers by Bernstein and ShamirTromer See httpcrypt0papershtmlnfscircuit httpwwwwisdomweizmannaciltr0mer high level design speci cation of basic components design of basic components and the entire system functional veri cation timing analysis What is a reconfigurable computer Microprocessor system I I I 5 lb 1m ih j Reconfigurable processor system Interface 5 Interface Characteristic Features close integration of the microprocessor system and the FPGA system integrated programming environment programming does not require hardware expertise suitable for a wide range of applications permits runtime reconfiguration of the FPGA system SRC vs FPGA Accelerator Boards Programming Graphical HDL Data Flow HLL FP G A Software Diagram Boards Hardware Software SRC Hardware LE SRC Compilation Process Application sources Macro sources Con guration Application bitstreams executable Run Time Reconfiguration in SRC Program in C or Fortran FPGA contents after the Function1 call Main program Function1 FPGA a Macro1a b c Macro2b d I Macro2c e Function2 Macro3s t Macro1n b Macro4t k 20 IDEAZ Module Multiglier Four Clock Delay um gt H mm 7 m Sheets Library Object 21 Star Bridge Compilation Process User input Graphical User Netlists Interface 1 Xil inx VIVA Place amp Route Con guration bitstreams Application executable SRC vs Star Bridge Programming Graphical HDL Data Flow HLL Software Diag ram quot SRC Hardware Software Star 39 quot b39 t Brldge Hardware porting L O Jecs EDIF Increased productivity Increased capability to describe parallel execution Project topics Analytical AS3 Analysis of existing electronic cash schemes and their implementations AS4 Comparison of protocols for secure mobile phone communications ASS Adhoc wireless network security protocols Prerequisites basics of cryptography computer network protocols Team 35 students Assumptions extensive literature study detailed metrics used for comparison security performance cost comparative analysis recommendations and predictions Project topics Analytical ACl Comparison of the ASIC FPGA and microprocessorbased implementations of classical cryptosystems Prerequisites basics of cryptography general knowledge of various semiconductor technologies and implementation approaches Team 13 students Assumptions extensive literature and market study detailed metrics used for comparison security performance cost comparative analysis recommendations and predictions 23 Projects Analytical Survey of Implementations AI3 Survey of the commercially available integrated circuits implementing cryptographic algorithms AI4 Comprehensive database of commercial and publicdomain programs for encryption of les and directories Projects Analytical Key management AIS Survey of software packages supporting Public Key In astructure AI6 Report on commercial Certi cation Authorities 24 ECE646 Lecture 10 RSA Implementation Efficient encryption Ef cient encryption decryption and decryption amp key generation 9 Number of bits vs number of decimal digits How to perform exponentlatlon eff1c1ently lomngiu2 bns YXEmodN modN x digits log10 2 39 bits 030 39 bits E39times E may be in the range of 21m x 10m8 256 bits 77 D 384 bits 116 D Fromm 512 bits 154 D 1 huge storage necessary to store XEbefore reduction 768 bits 231 D 2 amount of computations infeasible to perform 1024 bits308 D Solutions 2048 bits 616 D 1 modulo reduction after each multiplication 2 clever algorithms 2008C India Cl mndahS tra Righttoleft binary exponentiation Righttoleft binary exponentiation Example XE mod N Y 3 mod 11 Eet1yetzepenz 1191621100112 s X X2 mod N X4 mod N X8 mod N X2 mod N s X X2 mod N X4 mod N X8 mod N X mod N E en el 62 63 6L 3 32 mod 11 9 92 mod 11 4 42 mod 11 5 52 mod 11 3 e H e E en e1 e2 e3 e4 Y Xen X2 modN XAmod N 1 X8 modN 3 X2 39modN Lquot 1 1 0 0 1 I XabXab X2 X1 Xab Y X X2 modN 1 1 X1 modN en2e4e28e12 quot e 3 39 9 39 1 39 1 39 3m0d11 Y X mod N H X 9 mod N 2 ex 2 27mod113 mod 115 3 mod 11 4 X XEmodN Lefttoright binary exponentiation Y XE mod N E 6171 6er 61 602 E eLl eL2 eL3 el en Y11Xequotquot 1xeL21x e 2 ZXe XenmodN I Xab X2 X3 xb Xa I YXeL 2eL722eL732 e 2e Lefttoright binary exponentiation Example Y 3 mod 11 1191621100112 E e4 e3 e2 el en 1 0 0 1 1 Y 11 X 2 1 2 1 2 X2 X modN 732 mod 11 2 mod 112 mod 11 32 mod 11 3 mod 11 81 mod 111mod 1132mod 113mod 11 53Zmod113mod11 modN 4Zmod113mod11 L 5 3 mod 11 4 2Lquot emu e72 2L3 e73 2een 6 39 2 X mod N X i D XEmodN Y XEX1XmodNX 9modN Exponentiation Y XE mod N Exponentiation Example Y 712 mod 11 Rightitoilelt binary Le itoiright binary Rightitoilelt binary Le itoiright binary exponen atjon exponen atjon exponen atjon exponen atjon E9L7179L727 eien2 1211002 Y 1 S X for i0 to L1 for 1 dovmto 0 ife 1 XY1modN YYSmodN 1fe1 SS2modN YYXmodN Sh3mm S before round i is computed Sm S after round i is computed RighttoLeft Binary Exponentiation in Hardware output LefttoRight Binary Exponentiation in Hardware Basic Operations of RSA Time of exponentiation Enuyp m L lt k tE e L k modularimultiplicationse L tMULMODk El PM W PM e L modularimultiplications C M l mod I N l F3 2 ciphertext plaintext public key modulus 2 k bits k bits k bits e I4 2 1 17 Decryption Lk large random Lbit e L onese m 2 L private key tMULMODk time of a single modular multiplication M I I C I mOd I N oftwo kbit numbers modulo a kbit number mm ciphertext privatekey modulus k b k b k b SOFTWARE HARDWARE its I s I s tiiutMODGO Cm 39 k2 tMULiiouGO Chm 39 k Algorithms for Modular Multiplication PaperandPencil Algorithm of Multiplication lword lbyte A B B B Mumplim on x m B Assemon Zwurds Multi lication combined with Paperandpencil 901 modufar redumon g lg A DHDBD Karatsuba e 3H DiAoBi AiBo SchonhageStrassen FFl39 ek 1nk Momgomeiy algorithm D2AquotB2A B A2B D2 902 3 words 3 ms Modular Reduction DamAn3Bni Modal Mimi I 2 D2 Dag Anani Anan2 classical 9k I DMAMBM arre mplexity same as multiplication used 2 Words SelbyMitchell Z lcmlcml Icnxlcnlcxulcnzl ICxICuIC Classical Algorithm of Modular Reduction Time of basic operations in software and hardware x m l l X2 Km 32quot xiii q 7 XanbX2n2 q39n5 SOFTWARE HARDWARE nl 7 m 5012 Modular 39 Multiplication csm k chm k xmbxm q39 qmn mn 5012 Modular c kz L c kL Exponentiation 3 hm Time of the RSA operations as a function of the key size k SOFTWARE HARDWARE Encryption Signature veri cation cse k2 che k with a small exponent e Decryption 3 2 Signature generation csd39 k ch k Key 4 3 Generation c5k k log2k chkk log2k Factorization exmcsf klZ 1n k23 breaking RSA Effect of the increase in the computer speed on the speed of encryption and decryption in RSA to keep the same security computer operand speed size encryption decryption Q Decryption using Chinese Remainder Theorem M MF RQ MQ RF mod N Time of decryption Without and with Chinese Remainder Theorem SOFTWARE Without CRT tDEck tE random e k Lk cs k3 With CRT tDEcVCR k m 2 tmrandom e k2 Lk2 2 cs K tDEck HARDWARE Without CRT tDEck tmrandom e k Lk ch k2 can be represented uniquely by A gt a1 Amod n1 a2 Amod n1 aM Amod nM A can be reconstructed from a1 a2 aM using equation where N l M A 2 aiNi Ni391mod n9 modN n1 i1 nl nz n nMu nM where With CRT 71 Q71 RP 0 md Q P P quot m N tmmao tmuandom e m Lk2gt ch 51 RQ Q39l mod P Q Qquot modN 2 Chinese Remainder Theorem Chinese Remainder Theorem Let for NP Q Nnln1n3nM d 1 and N P Q gc R Q for any ij gcdn 11 1 7 7 Mlt Mp rMmodRMQrMmon Then any number 0 S A S N l PE 39lmodp MQ 39lmon MN MP Q Qquot mod P MQ P Pquot mod Q modN MF RQMQ RpmodN Concealment of messages in the RSA cryptosystem Blakley Borosh 1979 There e2a39st messages that are not changedby the RSA encryption For example M1 ClemodN1 M0 COemodN0 MN121modN C1emodN 1 Every M such that MpMmodPE101 MQMmon 5 10 1 CFCmodPMemodNmodP MemodP MpemodPMp CQCmodQMemodNmodQM 3monMQemonMQ Concealment of messages in the RSA cryptosystem Blakley Borosh 1979 At least 9 messages notcencealed by RSA Number ol messages not concealed by RSA c 1 gcde1 P1 1 gcde1 Q1 A39 23 0 9 B39 gcde1P1 2 and gcde1Q1 2 c 9 C39 gcde1P1P1 and gcde1 Ql Ql c PfN It is possible that all messages remain unconcealed by RSA Efficient key generation Generation of the RSA keys 8 Typically prime number generation P Q Extended Euclid is algorithm NPQ de391modP1 Q1 Random vs Incremental Search Random search primes numbers tested for primality Incremental search starting point chosen at random Is there a sufficent amount of prime numbers to choose from 7X the amount of prime numbers smaller thanx 0 X a 7X prime numbers Is there a sufficent amount of prime numbers of the given bit length to choose from nk the amount of prime numbers of the size of kbits 0 2krl 2k nk prime numbers nk 1t2k WZk39l m m 05 12k m 1t2k391 Average distance between primes of the given bit length 1 primes 21 i 2k Average distance between We consecutive primes I 2k 2101 2M Average distance k m m m 1n 2 1 m quotk 7t2k391 s 069 kl Average distance between primes of the given bit length 2 Number of bits Average distance Average amount k tween primes of odd numbers to test 256 177 88 384 265 132 512 354 177 1024 709 355 Fermat s primality test 11 composite Wn Witnesses to the compositness ofn 1n71 a e Wn in a 1 mod n Fermat s test 11 comp osite Carmichael numb er W n L a 2 8 Liars to the ompositness the compositness 0f ofn 1n71 Wn 51 1 Sa Sn gcda ngt1 l L01 PM l Wquot l nqKn Carmichael numbers A composite integer is a Carmichael number iff nP139Pz39p33939pk k23 p are distinct primes pfpJ for i j VP p1 nl Smallest Carmichael number n56l 3 ll 17 Among all numbers smaller or equal to 1015 There are about 3 1013 prime numbers 105 Carmichael numbers Good probabilistic primality test 11 composite Wn Witness es to the compositness of n V n composite Wn 2 Ln If a e Wn test returns 11 composite else test returns 11 probably prime or n pseudoprime to the base a Miller Rabin test 11 composite Wn Strong witnesses to the compositness 1n71 V n composite Ln g pn4 lt n 14 Miller Rabin test 11 composite W L Strong witnesses to the compositness Stron of the compo 1n71 For certain composite numbers such as 113 5 72k1 there are only two strong liars 1 and n 1 Miller Rabin test Mathematical Basis u is prime then 1 has only two square roots modulo n ie there are only two numbers yl and yz such that ylzmodn1 and y2 modn1 11 and yZZnlzl mod n u is composite then 1 has at least four square roots modulo n ie there exist numbers yl yz y3 y4 such that yl2 mod n 1y22 mod n1y32 mod n 1y42 mod n 1 y11y2n121 mod n y3 r 1 mod n y4 f r 1 mod n Miller Rabin test Algorithm 1 Find s and r such that n125r whererisodd For example n 49 n148243 543 n61 n160 22 15 52 F15 Miller Rabin test Algorithm 2 Compute a quot1 mod n ar mod n2 mod n2 mod n 2 mod n 1 s squarings square mod n 2 3 571 5 ar a 2 a 2 a 2 a 2 a 2 mod n square root mod n Miller Rabin test Algorithm 3 square mod n 1 S a 2 mod n ar2 r 2023 arzs39 L square root mod n result of test 1 1 1 1 1 1 X X 1 1 1 1 X X 1 1 1 1 1 1 1 1 1 1 X X X X X X X f r 1 mod n probably prime or composite 710g ol the bound on the error probability of declaring a k7bit composite number a prime alter t iterations of the Miller7Rabin test k number t number of iterations ofthe MillerRabin test of bits of n 1 2 3 4 5 5 7 8 9 10 100 5 14 20 25 29 33 36 39 41 44 150 8 20 28 34 39 43 47 51 54 57 200 11 25 34 41 47 52 57 61 65 69 250 14 29 39 47 54 60 65 70 75 79 300 19 33 44 53 60 67 73 78 83 88 400 37 46 55 63 72 80 87 93 99 105 500 56 63 70 78 85 92 99 106 113 119 600 75 82 88 95 102 108 115121 127 133 Minimal number of the Miller7Rabin tests t necessary to obtain the probability of error lt 2391quotquot for a k7bit number n Random vs Incremental Search Random search primes numbers tested for primality Incremental search starting point chosen at random Using di ion by small primes primes numbers tested A Y DDDDDDD DDDDDDDDDD R2 D 7 Division by small primes R2 7 MillerRabin test with base 2 R 7 MillerRabin test with the random base a 717171wa Merten s Theorem The proportion of candidate odd integers NOT ruled out by the trial division by all primes S aB113115 1 17 11B 013 112 In B For B255 1B m 02 80 of tested numbers discarded by the trial division Incremental searCh for 2 Prune Division by small primes Practical implementation 2 Efficient implementation of division by small primes 11 SM Set of small primes 11 nu91 namod113 32 mod 115 11 95 52 mod 117 11 97 72 mod 119 11 99 92 mod 11o n101 02 mod 112 Optimum number of small primes 351 Bow R 3quotquot D ln2R D 2 RSA countermeasures R2 time of the MillerRabin test with base 2 D time spent on test dividing one number by one small prime Recovering RSAencrypted messages without a private key 1 Recovering RSAencrypted messages without a private key 2 Guessing a set ol possible messages Small e and mallmermgex IRS FBI F3 00000000000000000 E publicikeyiofiFB name of the congress member who committed c m3 mod N m i m a tax fraud Hastad s attack l t F3 m send to three di erent people ouma is J E pumakekm nanen P 3 N m2 mod N1 E publicikeyiufiFEl nameZ U1 39 1 CRT 13 pU2 37 N2 m3 mod N2 439 m3 mod NINZN3 m3 439 m PUK 3 N3 m3 mod N3 E publicikeyiufiFEl WHEN ECE 646 Lecture 9 RSA Genesis operation amp security Public Key Asymmetric Cryptosystems Public key of Bob 7 KB Ju Encryption Decryption Private key of Bob 7 kB Alice Trap door one way function Whit eld Dif e and Martin Hellman New directions in cryptography 1976 PUBLIC KEY X fX Y f391Y PRIVATE KEY Professional NSA vs amateur academic approach to designing ciphers Know how to break Russian 1 Know nothing about ciphers cryptology Use only wellestablished 2 Think of revolutionary proven methods ideas Hire 50000 mathematicians 3 Go for skiing Cooperate with an industty 4 Publish in Scienti c giant American Keep as much as possible 5 Offer a 100 award for Secret breaking the cipher Challenge published in Scienti c American Ciphertext 9585 9513 7545 2205 1477 1409 2225 4355 8829 0575 9991 1245 7431 9874 5951 2093 0815 2982 2514 5708 3559 3147 5522 8839 8952 8013 3919 9055 1829 9451 5781 5145 Public key 114381625757 88886766923577997614 661201021829672124236256256184293 570693524573389783059712356395870 5058989075 147599290026879543541 e 9007 129 decimal digits Award 8100 RSA as a trapdoor oneway function RSA keys PUBLIC KEY PUBLIC KEY PRIVATE KEY M CfMMem0dN C e N d P Q M fquotC cd PRIVATE KEY N P Q P Q large pr1me numbers NPQ RQlargeprimenumbers e 39 d El m0dP391Q391 ed 2 1 mod P1Q1 Why does RSA work 1 7 M Cd modN ME mod Md mod N M decrypted original message message e d 21 mod P1Q1 i edzl modqN Euler s totient mcti on Euler s totient phi function 1 pN 7 number of integers in the range from 1 to N71 that are relatively prime with N Special cases 1 P is prime 91 PI Relatively pn39me with P 123 P1 2 NPQ PQareprime MN P1Q1 Relatively prime with N 1 2 3 PQl 71 2P 3P 21 QJQJQ 7P391Q Euler s totient phi function 2 Special cases 3 N P2 Pis prime NPP1 Relatively prime with N 1 2 3 PZl 7 P 2P 3P P1P In general IfNP1e1PZeZP3e3 Ptet ltpltN f1 ltP1 11 Euler s Theorem Leonard Euler 1 7071 783 V am 5 1 mod N a gcda N 1 Euler s Theorem Justification 1 For N10 For arbitrary N R1379 RXIXZX N Let a3 Let us choose arbitrary a such that gcdaN 1 S 31 mod 10 33mod 10 37 mod 10 39 mod 10 3 9 1 7 S axl mod N axzmod N ax Wmod N rearranged set R Euler s Theorem Justification 2 For N10 For arbitrary N R S R S 7 MN MN XI39XZ 39X3 39X4 7 1 ax2ax3ax4 modN H xI U a x mod N 11 1 xlxzx3lt4 zMN MN a x1xzx3xA modN H X all X modN 11 11 a4 E 1 modN a mo 2 1 modN Why does RSA work 2 M CdmodNMemodNdmodN 7 7 edzl moquN MedmOdN ed1kqN MHk Wm mod N M M PNkmod N M M PW mod Nk mod N Mlk modNM Rivest estimation 1977 The best known algorithm for factoring a 129digit number requires 40 000 trilion years 40 101 years assuming the use ofa supercomputer being able to perform 1 multiplication of 129 decimal digit numbers in 1 ns n y w 4 z z 1 J 39 z10ps Estimated age ol the universe 100 bln years 10 1 years Lehmer Sieve Bicycle chain sieve D H Lehmer 1928 Machine Congruences E O Carissan 1919 Computer Museum Mountain View CA Supercomputer Cray Early records in factoring large numbers n f7 a li Number of Reql red r 7 391 Years decimal NumPer computational of blts 1 IL in dlglts power in MIPS years 1974 45 149 0001 1984 71 235 0 1 199 1 100 3 32 7 1992 110 365 75 i 1993 120 398 830 Computer Museum Mountain View CA HOW to factor for free Practical implementations of attacks A Lenstra amp M Manama 1989 Factorization RSA Number Number of Usmg tlme spare tune of computers Year of bits decimal digits Method otherw1se unused ofN of N p 1994 430 129 Q5 5000 MIPSyears Program and results sent by e majl 1996 433 later using WWW 130 GNFS 750 MIPS years 1998 467 140 GN39FS 2000 MIPSyears 1999 467 140 GNFS 8000 MIPS year Breaking RSA 129 When August 1993 1 April 1994 8 months Who D Atkins M Graff A K Lenstra P Leyland 600 volunteers from the entire world How 1600 computers from Cray C90 through 16 MHz PC 0 fax machines Only 003 camputatianalpawer of the Internet Results of cryptanalysis39 The magic words are squeamish ossi age An award of 100 donated to Free Software Foundation Elements affecting the progress in factoring large numbers a computational power 19771993 increase of about 1500 times a computer networks Internet better algorith Factoring methods General purpose Special purpose Time of factoring is much shorter if N or factors of N are of the special form Time of factoring depends only on the size 0 GN39FS General Number ECM Elliptic Curve Method Field Sieve Pollard s pl method QS Quadratic Sieve l t 39 39 1 th d Continued Fraction Method Cyc 0 0mm pulynomla me 0 historical SNFS Special Number Field Sieve Running time of factoring algorithms Lam cl exp C01391n q 391n 1 1 For 10 La0 cl 1n trim For 11 La1 cl 6Xp001391n iv For 0ltult1 Algorithm polynonl39al as a function ofthe number ofbits ofq Algorithm exponential as a function ofthe number ofbits ofq Algorithm subexponemial as a function ofthe number ofbits ofq n 01 iffor any positive constant cgt0 there exist a constant n gt0 such that 0 S n lt c for all n 2 nu General purpose factoring methods Expected running time QS NFS Ln1211expltlt1alt1gtgtan mm In In M LNl3192exp192 al in N 1n1n M73 QS more NFS more mien mien l 00D 1 l D 1 0D 13 0D size ofthe factored number Nin decimal digits D First RSA Challenge RSAVIUU RSAVISU RSA200 RSAVASU RSAVASU RSAVAWU RSAVASU RSAVAQU RSAVSUU Largest number factored to date May 2005 Second RSA Challange Lentgh of N Length of N Award for in bits in decimal digits factorization Number of bits vs number of decimal digits 10 digiu 2min digits log10 2 bits 030 bits 256 bits 77D 384 bits 116 D 512 bits 154D 768 bits 31 D 1024bits308D 2048 bits616D Factoring 512 bit number 512 bits 155 decimal digits old standard for key sizes in RSA I7Mamh 22August 1999 Group of Herman te Riele Centre for Mathematics and Computer Science CWI Amsterdam First stage 2 months 168 workstations SGI and Sun 175400 MHZ 120 Pentium PC 300450 MHZ 64 MB RAM 4 stations DigitalCompaq 500 MHZ Second stage Cray C916 10 days 23 GB RAM Practical progress in factorization March 2002 Financial Cryptography Conference Nicko van Someren CTO nCipher Inc announced that his company developed software capable of breaking 512bit RSA key within 6weeks using computers available in a single office RSA vs DES Resistance to attack Number of operations in the best known attack NDES 150 NDES 512w RSA 567bit key Factoring RSA576 512 bits 155 decimal digits When Announced December 3 2003 Who J Franke and T Kleinjung Bonn University Max Planck Inm39tutefor Mathema cxin Bonn Expert39mentalMathematicsInxtimtemE en P Montgomery and H te Riele 7 CW1 F Bahr D Ledair P Leyland and R Wackerbarth German F ederalAgemy for Itybrmation Technology Security BIS Factoring RSA7200 200 decimal digits 664 bits When Dec 2003 May 2005 Wh 0 CW1 Netherlands 8mm University Pzan k Institute for Mathematics m 8mm Experimental Mathematics Manatee m ssen German Federal Agencyb Information Emma Technology Security 81S First stage About 1 year on Wrious machines equiwlent to 55 years on Opteron 22 GHz CPU Second stage 3 month on a cluster of 80 22 GHz Opterons connected via a Gigahit network Factoring RSA7640 640 bits 193 decimal digits When June 2005 Nov 2005 Wh 0 CW1 Netherlands Bdrm Unwemty Mar Planck 1mm arMaMematxcs m Bdrm Experimental Mathematics Manatee in Essen m mz Agency at In rmatnm Emquot Technology Security 81S First stage 3 months on 80 Opteron 22 GHZ CPUs Second stage 15 months on a cluster of 80 22 GHZ Opterons connected via a Gigahit network Factorization records decimal number myquot date umetnhzse 11 ataamnm c115 1113 1990 275MF Syeats was 120 w 1993 930 M PB yeat mans 129 1v1994 5000 M1F39S yeats mans 130 1v 19913 1000 M1F39S yeats ants 140 11 1999 2000 M1F39S yea s ants 155 V111 1999 9000 M1F39S yeats ants 12002 3 4 Pent1um1GHzCF U yeats ants 111 2003 2 7 Pent1um1GHzCF U yeats ants 132 Permum 16112 CPU yeats ants E 49 Pent1um1GHzCF Uyeats ants 200 VZEIEIE 121 Pent1um1GHzCF Uyeats ants Factorization records He Who has abso ute con dence 1n Mnear regresmon W111 expect 5 102471311 RSAnumberto be factored on ecemberW For themost recent records see Facwrila on Announcements at Estimation of RSA Security Inc regarding the number and memory of necessary to break RSA1024 Attack time 1 year Single machine PC 500 MHz 170 GB RAM Number of machines 342000000 Best Algorithm to Factor Large Numbers NUMBER FIELD SIEVE Complexity Subexponential tim e and memory N Number to factor k Number of bils of N Execution lime Exponential function ek Subrexponentiaifunctioii e Wonk Polynomial runcuom aw k Number of bils of N Factoring 1024bit RSA keys using Number Field Sieve NFS Polynomial Selection Relation Collection 200 b39t amp 350 bi smooth numbers Minifactoring Cofactoring Norm Factoring ECM p71 method rho method Linear Algebra Square Root TWINKLE The Weizmann INstitute Key Locating Engine Adi Shamir Eurocrypt May 1999 HES August 1999 Electrooptical device capable to speedup the rst phase of factorization from 100 to 1000 times If ever built it would increase the size of the key that can be broken from 100 to 200 bits Cost of the device assuming that the prototype was earlier built 5000 Bernstein s Machine 1 Fall 2001 Daniel Bernstein professor of mathematics at University of Illinois in Chicago submits a grant application to NSF and publishes fragments of this application as an article on the we D Bernstein Circuits for Integer Factorization A Proposal httpcryptopapers htmlnfscircuit Bernstein s Machine 2 March 2002 Bernstein s article discovered during Financial Cryptography Conference Informal panel devoted to analysis of consequences of the Bernstein s discovery 0 Nicko Van Someren nCipher estimates that machine costing 1 bilion is able to break 1024bit RSA within several minuts Bernstein s Machine 3 March 2002 0 alarming voices on emailing discussion lism calling for revocation of all currently used 1 024bit keys 0 sensational articles in newspapers about Bernstein s discovery Bernstein s Machine 4 April 2002 Response of the RSA Security Inc Error in the estimation presented at the conference according to formulas from the Bemstein s article machine costing 1 billion is able to break 24 bit RSA within 10 billion X several minuts tens of years According to estimations of Lenstra i Verheul machine breaking 1024 bit RSA within one day would cost 160 billion in 2002 Bernstein s Machine 5 Carl Pomerance Bell Labs fresh and fascinating idea Arjen Lenstra Citibank amp U Eindhoven I have no idea what is this all fuss about Bruce Schneier Counterpane enormous improvements claimed are more a result of rede ning e iciency than anything else Bernstein s Machine 6 RSA keylength that can be broken TWIRL February 2003 Adi Shamir amp Eran T mmer Weizmann Institute of Science using Bernstein s machine Hardware implementation of the Sievmg phase of RSAkey lengths that canbe broken Number Field Sieve NFS using classical computers 3 f Assumed technolog 2 CMOS 013 mm 7 7 clock 1 GHZ 1 7 7 30 cm semiconductor wafers at the cost of 5000 each 39 s 1 bln1 day s 1000 bln1 day in nity r 39 time days memory TWIRL A Shamir E Tromer Crypto 2003 Tentative estimations no experimental data 512bit RSA lt 10 minutes 10 k 1024bit RSA lt 1 year 10 million Theoretical Designs for Sieving 1 1 9992000 TWINKLE Shamir CHES 1999 Shamir amp Lenstra Eurocrypt 2000 based on optoelectronic devices fast LEDs not even a small prototype built in practice not suitable for 1024 bit numbers m TWIRL Shamir amp Tromer Crypto 2003 semiconductor wafer design requires fast communication between chips located on the same 30 cm diameter wafer dif cult to realize using current fabrication technology Theoretical Designs for Sieving 2 2003 2004 Mesh Based Sieving YASD Geiselm ann amp Steinwandt PKC 2003 Geiselmann amp Steinwandt CT RSA 2004 not suitable for 1024 bit numbers 2005 SHARK Franke et al SHARCS amp CHES 2005 relies on an elaborate butter y switch connecting large number of chips difficult to realize using current technology Theoretical Designs for Sieving 3 2007 Non Wafer Scale Sieving Hardware Geiselmann amp Steinwandt Eurocrypt 2007 based on moderate size chips 22 x 22 cm communication among chips seems to be realistic 2 to 35 times slower than TWIRL supports only linear sieving and not more optimal lattice sieving Estimated recurring costs with current technology USxyear by Eran Tromer May 2005 768bit 1024bit Traditional 13gtlt107 1012 PCbased TWINKLE 8gtlt106 TWIRL 5x103 10gtlt106 Meshbased 3x104 SHARK 230x106 But non recurring costs chip size chip transport networks However None of the theoretical designs ever built Just analytical estimations no real implementations no concrete numbers First Practical Implementation of the Relation Collection Step in Hardware 2007 m7 rmquot pmauslamrhase re m III lnl rm Japan Tetsuya lzu and Jun Kogure and Takeshi Shimoyama Fujitsu CHES 2007 CAIRN 2 machine September 2007 SHARCS 2007 CAIRN 3 machine September 2007 First large number factored using FPGA support Factored number N P Q 423bits 205 bits 218 bits Time of computations One month of computations using a PC supported by CAIRN 2 for a 423 bit number CAIRN 3 about 40 times faster than CAIRN 2 Time of sieving with CAIRN 3 for a 768 bit key estimated at 270 years Problems Speed up vs one PC AMD Opteron only about 4 times Limited scalability 10 Workshop Series SHARCS Special purpose Hardware for Attacking Cryptographic Systems 1st edition Paris Feb 2425 2005 2quot 1 edition Cologne Apr 34 2006 3rd edition Vienna Sep 910 2007 See Keylengths in public key cryptosystems that provide the same level of security as AES and other secretkey ciphers en K Lenstra Eric R Verheul Selecting Cryptographic Key Sizes Journal of Cryptology en K Lenstra Unbelievable Security Matching AES Security Using Public Key Systems ASIACRYPT 2001 Keylengths in RSA providing the same level of security as selected secretkey cryptosystems The same cost AESJZS AE8719Z AE87256 2 kevs 3 kevs Keylengths in RSA providing the same level 2030 year Recommended key sizes for RSA RSA Laboratories 1996 hi 155 ma 39 39ts 768 bits 231 decimal digits Old standard Individualusers New standard Individual users 1024 bits 0 11 h 1 1 rgamza 039 s or enquot 308 decimal digits Organizations long term 2048 hits 616 decimal digits Recommendations of RSA Security Inc May 6 2003 Minimal Equivalent symmetric Validity period RSA key length 5 bits 20032010 1024 80 20102030 2048 112 2030 3072 128 Five security levels allowed by American government NIST SP 80056 Level RSA I DH ecc 534mg 1024 160 80 II 2048 224 112 Ill 3072 256 128 IV 8192 384 192 V 15360 512 256 Discovery of public key cryptography by British Intelligence CESG CommunicationsElectronics Security Group British intelligence agency existing for over 80 yers Employees of CESG discovered the idea of public key cryptography the RSA cryptosystem and the DiffieHellman key agreement scheme several years before their discovery in open research Story disclosed only in December 997 Secret research JamesH Ellis The possibility of Secure NonSecretDigital Encryption January 1970 proof ofa possibility of constructing nonsecretkey cxyptography General concept of public key cryptography Open research Whit Diffie Martin Hellman New Directions in Cryptography November 1976 example ofa publickey agreement sc eme concept ofa digital signature RSA cryptosystem Secret research Open research Clz ord Cocks Ron Mvest Adi Shamir Martin Hellman November 1973 January 1978 CMNmodN CM modN Decryption always based on the Chinese Remainder Theorem Decryption has ed on the Chinese Remainder Theorem optional Diffie Hellman Key Agreement Scheme Secret Research Malcolm Williamson 1974 Open Research Whit Diffie Martin Hellman June 1976 Discovery of the public key cryptography by British Intelligence 0 Discovery in the secret research had only historical significance Discovery in the open research initiated the revolution in cryptography 0 British Intelligence never considered applying public key cryptography for digital signatures 0 It is still unclear whether and if so when public key cryptography was discovered by NSA 72 ECE 646 Lecture 6 Historical Ciphers Why not to study historical ciphers AGAINST FOR Basic components became a part of modern ciphers Not similar to modern ciphers Under special circumstances Long abandoned modern ciphers reduce to historical ciphers In uence on world events The only ciphers you can break Secret Writing Steganography Cryptography hidden messages encrypted messages Substitution Transposition Transformations Ciphers change the order of letters Codes Substitution replace Clphers words replace letters Selected world events affected by cryptology 1586 trial of Mary Queen of Scots substitution cipher 1917 Zimmermann telegram America enters World War I 193 91 945 Battle of England Battle of Atlantic D day ENIGMA machine cipher 1944 world s first computer Colossus German Lorentz machine cipher 1950s operation Venona breaking ciphers of soviet spies stealing secrets of the US atomic bomb onetime pad Ciphers used predominantly in the given period1 Cryptography Cryptanalysis 100 BC Shift ciphers Frequency analysis alKindi Baghdad 1X C Monoalphabetic substitution cipher 1586 Invention of the Vigen ere Cipher Black chambers Homophonic ciphers XVIII c39 Vigenere cipher Kasiski s method 1863 Simple polyalphabetic substitution ciphers 1919 Invention ofrotor machines Index of coincidence 1918 William Friedman Electromechanical machine ciphers Complex polyalphabetic substitution ciphers 1926 Vernam cipher onetime pad Ciphers used predominantly in the given period2 Cryptography Cryptanalysis Reconstructing ENIGMA 1932 Rejewski Poland Polish cryptological bombs an forated sheets 1949 Shennon s theory 1939 0 secret systems une time pad British cryptological Stream Ciphers bombs Bletchley Park UK 1945 Sip networks Breaking Japanese 1977 Publication of DES Purple PW 1977 DES Triple DES 1990 DES crackers 2001 2001 AES Substitution Ciphers 1 l Monalphabetic simple substitution cipher M m1 m2 m3 m4 mN C fm1 fm2 fm3 fm4 fmN Generally f is a random permutation eg abcdefghijklmnopqrstuvwxyz sltavmcerubqufkhwygxzjnior Key f Number of keys 26 a 4 1026 Monalphabetic substitution ciphers Simplifications 1 A Caesar Cipher ci fmi mi 3 mod 26 mi f 1ci ci 3 mod 26 No key B Shift Cipher ci fmi mi k mod 26 mi f 1ci ci k mod 26 Key k Number of keys 26 Coding characters into numbers AltgtO Nltgtl3 Bltgtl Oltgtl4 Cltgt2 Pltgt15 Dltgt3 Qltgtl6 Eltgt4 Rltgtl7 Fltgt5 Sltgt18 Gltgt6 Tltgt19 Hltgt7 Ultgt20 Iltgt8 Vltgt21 Jltgt9 Wltgt22 KltgtlO Xltgt23 Lltgtll Yltgt24 1V1lt2gt12 Zltgt25 Caesar Cipher Example Plaintext I CAME I SAW I CONQUERED 8 20124 818022 8 214131620 41743 1153157112132511517161923 7 207 6 Ciphertext LFDPH LVDZ L FR QTXHUHG Monalphabetic substitution ciphers Simplifications 2 C Affine Cipher ci fn1i k1 mi k2 mod 26 gcd k1 26 1 mi f 1ci k1 391 ci k2 mod 26 Key 2 k1 k2 Number ofkeys 1226 312 Most frequent single letters Average frequency in a random string of letters i 0038 38 26 Average frequency in along English text E 13 T N R I O A S 69 D H L 3545 C F P U M Y G W V l53 BXKQJZ ltl Most frequent digrams and trigrams Digrams TH HE IN ER RE AN ON EN AT T rigrams THE lNG AND HER ERE ENT THA NTH WAS ETH FOR DTH Relative frequency of letters in a long English text by Stallings 0 ABCDEFGHIJKLMNOPQRSTUVWXYZ Character frequency in a long English plaintext abodefghijklmnopqrstuvwxyz Character frequency in the corresponding ciphertext for a shift cipher abodefghijklmnopqrstuvwxyz Character frequency in a long English plaintext O N a o abodefghijklmnopqrstuvwxyz Character frequency in the corresponding ciphertext for a general monoalphabetic substitution cipher abodefghijklmnopqrstuvwxyz Frequency analysis attack relevant frequencies oNJso oo abcdefghljklmnopqrstuvwxyz jklmnopqrstuvwxyz Long English text T Short English message M 8 6 4 2 0 abcdefghljklmnopqrstuvwxyz abcdefghljklmnopqrstuvwxyz Ciphertext of the long English text T Ciphertext of the short English message M Frequency analysis attack 1 Step 1 Establishing the relative frequency of letters in the ciphertext Ciphertext FMXVE DKAPH FERBN DKRXR SREFM ORUDS DKDVS HVUFE DKAPR KDLYE VLRHH RH ABCDEFGHIJKLMNOPQRSTUVWXYZ R 8 D 7 EHK 5 Frequency analysis attack 2 Step 2 Assuming the relative frequency of letters in the corresponding message and deriving the corresponding equations Assumption Most frequent letters in the message E and T Corresponding equations E gtR fE R T gtD fT D 4 17 f417 l9 gt3 f1923 Frequency analysis attack 3 Step 3 Verifying the assumption for the case of affine cipher f4 17 f19 3 Q 4k1 k2 E 17 mod 26 19k1 k2 E 3 mod 26 Q 15k12 14 mod 26 Q 15k1 E 12 mod 26 Substitution Ciphers 2 2 Polyalphabetic substitution cipher M m1 m2 md md1 md2 m2d m2d1 m2d2 m3d f11111 f2m2 fdmd f1md1 f2md2 fdm2d f1m2d1 f2 m2d2 fdm3d d is a period of the cipher Key 1 f1 f2 fd Number of keys for a given period 1 26d 2 4 1026d abodefghijklmnopqrstuvwxyz Character frequency in a long English plaintext Character frequency in the corresponding ciphertext for a polyalphabetic substitution cipher i1 100 38 quotn 26 abodefghijklmnopqrstuvwxyz Polyalphabetic substitution ciphers Simplifications 1 hift cipher lCS lgenere cipher polyalphabet39 AV Invented in 1568 f1 mod 10111 2 mi k1 modd mOd 26 Ci mi kimOdd mod 26 f1i mod dmi mi 2 kdl Keyk0 k1 26d Number of keys for a given period 1 Square abcdefghljklmnopqrstuvwxyz 1gen re V abcdefghljklmnopqrstuvwxyz 3 plaintext mnopqrstuvwxyzabcde nopqrstuvwxyzabcdef Key nsa opqrstuvwxyzabcdefghljklmn uvwxyzabcdefghljklmnopqrst zabcdefghljklmnopqrstuvwxy 12 Vigenere Cipher Example Plaintext TO BE OR NOT TO BE Key NSA Enc ti0n T O B ryp E O R NOT TOB E GGB RGR AGT GGB R Ciphertext GGBRGRAGTGGBR Determining the period of the polyalphabetic cipher Kasiski s method CipherteXti GGBRGRAGTGGBR Distance 9 Period d is a divisor of the distance between identical blocks of the ciphertext In our example 1 3 or 9 Index of coincidence method 1 nl number of occurances of the letter 139 in the ciphertext 139 a z N length of the ciphertext pi frequency of the letter 139 for a long ciphertext mi N pi lim N gt ltgtltgt ZPFI Index of coincidence method 2 Measure of roughness 2 Z 1 Z l MR 7 2 7 le 26 Zquot 26 139 a 139 a MR 0028 0014 0006 0003 period 1 2 5 10 Index of coincidence method 3 Index of coincidence Z The approximation of Z pf Definition 1 Probability that two random elements of the ciphertext are identical 2 Formula Z Hi 2 nilni 102 2 ia ia m Index of coincidence method 4 Measure of roughness Z Z mi1 m ia MR 0028 0014 0006 0003 period 1 2 5 10 Polyalphabetic substitution ciphers Simplifications 2 B Rotor machines used before and during the WWII Country Machine Period Germany Enigma d262526 16900 U SA M325 Hagelin M209 Japan Purple UK39 TypeX d2626k26 k5 7 9 Poland Lacida d243 1 35 26040 Substitution Ciphers 3 3 Runningkey cipher M m1 m2 m3 m4 mN K k1 k2 k3 k4 kN K is a fragment of a book C c1 c2 c3 c4 cN ci mi ki mod 26 mi ci ki mod 26 Key book title edition position in the book page row Character frequency in a long English plaintext abodefghijklmnopqrstuvwxyz Character frequency in the corresponding ciphertext for a runningkey cipher 100 38 quotn 2 0 abodefghijklmnopqrstuvwxyz Substitution Ciphers 4 4 Polygram substitution cipher M H11 H12 n1d M1 md1 md2 m2d 39 M2 m2d1 m2d2 m3d 39 M3 C c1 c2 cd C1 Cd1 Cd2 c2d 39 C2 c2d1 c2d2 03d 39 C3 1 is the length of a message block Ci fMi Mi f391Ci Key d f Number of keys for a given block length d 26d Playfair Cipher 1854 Key PLAYFAIR IS A DIGRAM CIPHER Convention 1 message P O L A N D ciphertext A K A Y Q R Convention 2 message P O L A N D ciphertext K A R S R Q Ciphering C1xd M1xd 39 Kdxd kn kn k1d chcz cdm1m2 md kdl kd2 cz39phertext block message block key matrix Hill Cipher Deciphering M1xd C1xd 39 K1dxd message block ciphertext block inverse key matrix Where 1000 0100 Kdxd39K391dxd 00l0 000l key matrix inverse key matrix identity matrix Hill Cipher Known Plaintext Attack 1 Known C1 3112012201d M1m11m12m1d C2 021 022 02d M2 121 m22 mZd Cd Cal Cd2 cdd Md mdla md2 mdd We knowthat 011 c12 01d 201111 11112 1AIlld39Kdxd 021 c22 02d 2 11121 11122 mzd 39 Kdxd cdl cdz cdd md1 mdz mdd Kdxd Hill Cipher Known Plaintext Attack 2 kn kn k1d 011012 cldl m11m12 m1d 21 22 02d 2 H121 H122 m2d k21 k2 kzd cd1 c12 cdd md1 md2 mdd kdl kdz kdd Cdxd Mdxd 39 Kdxd Kdxd M1dxd 39 Cdxd Substitution Ciphers 5 4 Homophonic substitution cipher MABCZ C012399 ci fmi random number mi W01 f E gt 1719 27 48 64 A gt 8 20 25 49 U gt 45 68 91 X gt 33 20 Transposition ciphers M m1 m2 m3 m4 mN C mf mf2 mf3 mm mfm Letters of the plaintext are rearranged without changing them Character frequency in a long English plaintext abodefghijklmnopqrstuvwxyz Character frequency in the corresponding ciphertext for a transposition cipher abodefghijklmnopqrstuvwxyz Transposition cipher Example Plaintext CRYPTANALYST Key KRIS 23 14 Encryption KRI S CRYP TANA LYST Ciphertext YNSCTLRAYPAT Onetime Pad Vernam Cipher Gilbert Vernam ATampT 1926 A yoerseph dauborgne ci mi 43 ki mi OlllOllOlOlOOlOlOllOlOl ki llOlllOlllOllOlOlllOllO c lOlOlOllOllllllllOOOOll 1 All bits of the key must be chosen at random and never reused 22 Onetime Pad Equivalent version ci n1i ki mod 26 m TO BE OR NOT TO BE 1 k AX TC VI URD WM OF 1 q TL UG JZ HFW PK PJ All letters of the key must be chosen at random and never reused Perfect Cipher Claude Shannon Communication Theory of Secrecy Systems 1948 V PMmCcPMm meM 06C The cryptanalyst can guess a message with the same probability without knowing a ciphertext as with the knowledge of the ciphertext 23 Is substitution cipher a perfect cipher C XRZ PMADD CXRZ 0 PMADD 72 0 Is onetime pad a perfect cipher C XRZ PMADD CXRZ 7t 0 PMADD 7t 0 M might be equal to CAT PET SET ADD BBC AAA HOT HIS HER BET WAS NOW etc 24 SP Networks 3 3 3 Basic operations of SP networks Substitution Permutation Oi b ID OOO o o IIIII OD OOb ID IO IIIII OD lb lD OOO S box Pbox 25 Avalanche effect 8 gt gt gt gt gt gt gt 8 gt gt gt gt gt gt p p gt gt gt gt gt gt gt gt S39 gt gt gt S39 gt gt S C a c2gt C2 95497 5 7 c7gt c7 c8 c8 C5 Cm c 952 7 954 954 62 Horst Feistel Walt Tuchman IBM km km kms m gt cl m2 gt c2 m3 gt gt c3 quot 4 39 c4 km k2 K216 quot 5 gt gt gt gt 95 quot 5 gt gt gt gt c6 quot 7 gt gt gt c7 m8 gt gt gt gt km P K32 P k316 m 9 mm b p gt gt cm quot 11 gt gt gt gt 11 mil CIZ k3Z1 k3ZZ lk3216 quot 12 gt gt gt Cu m2 gt gt C125 quot 12 CH7 leX 3 28 16 rounds 26 ECE 646 Lecture 7 Towards modern ciphers Data Encryption Standard and its extensions Encryption C1xd M1xd 39 Kdxd kn kn k1d c1 c2 Cd m1m2 1nd kdl kd2 cz39phertext block message block key matrix Hill Cipher Decryption M1xd C1xd 39 K1dxd message block ciphertext block inverse key matrix Where 1000 0100 Kdxd39K1dxd 0010 0001 key matrix inverse key matrix identity matrix Hill Cipher Example 1 K 2 Z X 25 23 dxd 1 X 08 23 K4 2 23 03 Z X D dxdl 18 257 s Zr 25 23 23 03 1 0 1 Kdquotd K dxdl 08 23 18 25 0 1 Hill Cipher Example 2 Encryption message C I P H E R C I 25 23 C1x2 MW KW 02 08 i 08 23 Z 0225 0808 mod 26 02 23 0823 mod 26 10 22 K W Decryption K W 23 03 Mlx2 Clx2 39K3912x2 10 22 18 25 1023 2218 mod 26 1003 2225 mod 26 02 08 C D Hill Cipher Known Plaintext Attack 1 Known C1011 012 cld M1 H111 m12 mld C2 C21 022 02d M2 121 m2 mZd Cdcd1 Cd2 cdd Md mdla md2 mdd We know that 011 c12 Cid 201111 m12 1AIlld39Kdxd C21 c22 C26 2 11121 m22 m2d 39 Kdxd cdl cdz cdd md1 md2 mdd Kdxd Hill Cipher Known Plaintext Attack 2 kn kn k1d c11c12quot39c1d m11m12 3939m1d 21 22 02d 2 H121 H122 m2d k21 k2 kzd Cal 012 cdd map md2 mdd kdl kdz kdd Cdxd Mdxd 39 Kdxd Kdxd M1dxd 39 Cdxd Onetime Pad Vernam Cipher Gilbert Vernam ATampT 1926 Major Joseph Mau borgne ci1ni ki mi OlllOllOlOlOOlOlOllOlOl ki llOlllOlllOllOlOlllOllO C lOlOlOllOllllllllOOOOll 1 All bits of the key must be chosen at random and never reused Onetime Pad Equivalent version ci n1i ki mod 26 m TO BE OR NOT TO BE 1 k AX TC VI URD WM OF 1 q TL UG JZ HFW PK PJ All letters of the key must be chosen at random and never reused Perfect Cipher Claude Shannon Communication Theory of Secrecy Systems 1948 V PMmCcPMm meM 06C The cryptanalyst can guess a message with the same probability without knowing a ciphertext as with the knowledge of the ciphertext Is substitution cipher a perfect cipher C XRZ PMADD CXRZ 0 PMADD 72 0 Is onetime pad a perfect cipher C XRZ PMADD CXRZ 7t 0 PMADD 7t 0 M might be equal to CAT PET SET ADD BBC AAA HOT HIS HER BET WAS NOW etc SP Networks 3 3 3 Basic operations of SP networks Substitution Permutation Oi b ID OOO o o IIIII OD OOb ID IO IIIII OD lb lD OOO S box Pbox Avalanche effect 8 gt gt gt gt gt gt gt 8 gt gt gt gt gt gt p p gt gt gt gt gt gt gt gt S39 gt gt gt S39 gt gt S C a c2gt C2 95497 5 7 c7gt c7 c8 c8 C5 Cm c 952 7 954 954 62 W W N quotU gt gt gt gt km gt gt K3 P 1922 Horst Feistel Walt Tuchman IBM kms gt c c2 C gt CA K216 c5 c6 c7 gt k316 gt gt CID H CH l k3Z16 gt c125 c126 gt c m gt 16 rounds LUCIFER external look plaintext block LUCIFER h key 512 bits 128 bits ciphertext block NBS public request for a standard cryptographic algorithm May 15 1973 August 27 1974 The algorithm must be secure public completely specified easy to understand available to all users economic and ef cient in hardware able to be validated exportable DES chronicle of events 1973 NBS issues a public request for proposals for a standard cryptographic algorithm 1975 rst publication of the IBM s algorithm and request for comments 1976 NBS organizes two workshops to evaluate the algorithm 1977 official publication as FIPS PUB 46 Data Encryption Standard 1983 1987 1993 recertiflcation of the algorithm for another ve years 1993 software implementations allowed to be validated Controversies surrounding DES Unknown Slow Too short design in software key criteria Most criteria h Odnly I reconstructed lar Wfrte Theoretlcal from Cipher 1mp emen a ions deSIgns analySis cem ed of DES breaking machines 1990 39 39 1993 1998 RemVemlOn Software rmware P t 1 of differential and hardware DEgac 10 CryptanaIYSiS treated equally big er 1970 1 DES developed by IBM and NSA De Life of DES 980 1990 2000 Time transision to a new standard In common use for over 20 years Federal and banking standard Over 300 validated implementations facto worldwide standard Most popular secretkey ciphers 1980 1990 2000 2010 2020 2030 1977 19991 3 I 112 168 b1t keys was 1 Tnpl39e DES 1 3 1 American 56 bit key AES Rijndael Standards AES 2001 128 192 and 256 bit keys contest IDEA Serpent Other popular RC5 iTwofish 31 th Blow sh RC6 CAST Mars DES external look plaintext block 64 bits ciphe ext bloc DES highlevel internal structure 7 m uvhumr Pigm 37 nunm nq umm 0 ms Encryplion lguri lm DES Main Loop Feistel Structure Ln1 Rn Rn anB Kn Feistel Structure Encryption Decryption Decryption Mangler Function of DES F K as his Figure 39 Calculation of HR K 11gt Inmm 39unnll1l1nll urn a 0 13 U n I 1H 1H 39 H 39h 2b quot1 l I 1 n 411 m 1H 11 1 b r M m 12 I 11 7 I H 1 1 3 17 I l u 4 1 7 139 N H 1 m 8 Ilt 1 1 30 Al 4 1quot 85 I7 w 1 31 IS quot 1 lmuw Imlml l39ummuwru H39 quot 1 U 1 H 391 v 14 1 39 8 lt ll 11 s A H u T39 w l v I n 1 1 H I Input Notation for Permutations 391 392 393 394 395 396 397 398 399 3910 3956 3957 3958 3959 3960 3961 3962 3963 3964 5850 4234261810 2 5635547393123157 3958 3950 3942 3934 3926 3918 3910 392 395 3963 3955 3947 3939 3931 3923 3915 397 Output l IIIIIu J I39III IIIIII UI mm 54 wa H II I I 2 I5 1 5 3 III I I i I II 7 x II I 7 I I4 1 I3 I In a II II I s s I I H a I I 2 II 15 I u 1 I In a II 5 I X I 4 I I 7 lt H 3 H II II I l1 I I I s K II I4 6 II I I I 7 II I II III s J H 4 7 1 5 II I II I I0 I I II 5 0 III 7 II III 4 I I i x I lt I I I I N III I H I I1 7 I II II I III II I I4 I I IS I H Iz II I x 5 I 7 II I I I I III II 5 II I II I I H 4 II 5 I II II I 2 I2 II II 7 I III 3 II I 9 II 7 I I H I II 1 I 13 H 1 II I III 1 A II I I I N I 5 II n Ii II 3 4 7 I III II II 6 I II II 7 I I l I H I 5 U I I3 8 I I II I I II II If II PI II I l7 I 10 I I H II II 7 J 1 I III II 7 l I I I I 4 II II I7 I 7 H I H I II I 3 I II II I I III 7 I IN II I I I 4 I I Is 11 I III I I4 II I 7 x I Ii I I III R I I i I II II II I 7 II 4 1 II I I II III II I5 I I H 7 I III N 11 IN I I II I lt I II Notation for Sboxes Input i1 i2 i3 i4 i5 i6 i1 i6 determines a row number in the Sbox table 03 i2 i3 i4 i5 determine a column in the Sbox table 015 Q1 02 03 04 is a binary representation of a number from O 15 in the given row and the given column 01 02 03 04 Output 1 32 bits b 4 3 him b 4 23 hits Dr 4 23 bits Iv I m I Left shifttsl Left shiftts Expansion permutation 1E table Iv Pemmtatium39contraction 43 1 Permutedl Choice 2 Substitutiomelmice ITSbox Figure 38 Single Round of DES Algorithm 2 Input Key 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 b Permuted Choice One PCl 57 49 41 33 25 17 9 1 58 50 42 34 26 18 10 2 59 51 43 35 27 19 11 3 60 52 44 36 63 55 47 39 31 23 15 7 62 54 46 38 30 22 14 6 61 53 45 37 29 21 13 5 28 20 12 4 c Permuted Choice Two PC2 14 17 11 24 1 5 3 28 15 6 21 10 23 19 12 4 26 8 16 7 27 20 13 2 41 52 31 37 47 55 30 4O 51 45 33 48 44 49 39 56 34 53 46 42 50 36 29 32 d Schedule of Left Shifts Roundnumber 12 3 4 5 6 7 8 910111213141516 Bitsrotated 1122222212222221 General design criteria of DES 1 Randomness 2 Avalanche property changing a single bit at the input changes on average half of the bits at the output 3 Completeness property every output bit is a complex function of all input bits and not just a subset of input bits 4 Nonlinearity encryption function is nonaf ne for any value of the key 5 Correlation immunity output bits are statistically independent of any sub set of input bits Completeness property Every output bit is a complex function of all input bits and not just a subset of input bits Formal requirement For all values ofi andj i164jl 64 there exist inputs X1 and X2 such that X1 x1 x2 x3 xi1 0 xi x63 x64 X2 x1 x2 x3 xi1 l xi x63 x64 Y1 DESX1 Y1 Y2 Y3 Yj1 Yj1 Y63 Y64 Y2 DESX2 Y1 Y2 Y3 Yj1 Yj YjH 363 364 Linear Transformations Transformations that fulfill the condition TXmx 1 Ynx l Anxm 39 Xmx 1 Of TX1 93 X2 TX1 lt9 TX2 Affine Transformations Transformations that fulfill the condition TXmxl Ynxl Anxm 39 Xmxl EB Bnxl Linear Transformations of DES 1P IP l E PCl PC2 SHIFT e g 1PX1 9 X2 1PX1 911309 NonLinear and nonaffine transformations of DES S There are no such matrices AWG and B 4X1 that SX6xl A4x6 39 X6xl ea B4x1 Design of Sboxes SO15 gt S gt in 16 a 2 1013 possibilities precisely defined initially unpublished criteria resistant against differential cryptanalysis attack known to the designers and rediscovered out Sin in the open research in 1990 by E Biham and A Shamir Typical Flow Diagram of a SecretKey Block Cipher Round KeyO l Round Keyi Cipher Round rounds times Round Keyrounds 1 Final transformation 20 Implementation of a secretkey cipher in hardware Round keys computed onthefly input key i key encryption decryption scheduling 1 round keys output Implementation of a secretkey cipher Round keys precomputed input key v key scheduling encryptiondecryption I 1 memory of round keys output 21 Basic iterative architecture of secret key ciphers 1n ut V k multiplexer By 1 1 Key scheduling round keys output Theoretical design of the specialized machine to break DES Project Michael Wiener Entrust Technologies 1993 1997 Method exhaustive key search attack Basic component specialized integrated circuit in CMOS technology 75 MHz Checks 200 mln keys per second Costs 10 Total cost Estimated time 1 mln 35 minutes 100000 6 hours 22 DES breaking machine 1 Round Encryption Round 1 I known ciphertext Key Scheduling Round 1 Encryption Round 2 Key Scheduling Round 2 Round key 2 Encryption Round 16 Key Scheduling Round 16 Round key 16 plaintext comparator known plaintext Deep Crack Electronic Frontier Foundation 1998 Total cost 220000 Average time of search 45 dayskey 1800 ASIC chips 40 MHz clock 23 Deep Crack Parameters Number of ASIC chips 1800 Clock frequency 40 MHz Number of clock cycles per key 16 Number of search units per ASIC 24 Search speed 90 bln keyss Average time to recover the key Minimum length of the key for symmetric ciphers 1 Panel of experts January 1996 M Blaze W Dz ie R Rivest B Schneier T Shimomura E Thompson M Wiener Report Minimal Key Lengths for Symmetric Ciphers to Provide Adequate Commercial Security 11 National Academy of Sciences National Research Council May 1996 Report Cryptography s Role in Securing the Information Society Minimum key length for symmetrickey ciphers Intruder Budget Tools Time secure 40 bits 56 bits key length Hacker tiny PC 1 week infeasible 45 Small 400 FPGA 5 1113 38 yeais 50 business 10000 FPGA 12 min 18 months 55 C t FPGA 24 sec 19 da s d orpftm e t 300 K y 60 9399 me ASIC 18 sec 3 hrs 339 FPGA 7 sec 13 hrs 70 lg 10 M company ASIC 5 ms 6 min Intelligence 300 M ASIC 02 ms 12 sec 75 agency Secure key length today and in 20 years key length 94 bits 80 bits 7 128 bits 120 bits 1 12 bits 7 56 bits DES 80 bits Skipiack Secure key length in 2002 Secure key length in 2022 IDEA minimum key length in AES DESX Triple DES with two keys 25 Secure key length discussion increasing key length in a newly developed cipher costs NOTHING increasing effective key length assuming the use of an existing cipher has a limited in uence on the efficiency of implementation DESX Triple DES It is economical to use THE SAME secure key length FOR ALL aplications The primary barriers blocking the use of symmetric ciphers with a secure key length have been of the political nature e g export policy of USA Other attacks 0 differential cryptanalysis Biham Shamir 1991 0 linear cryptanalysis Malsul39 1993 26 Differential cryptanalysis key Mi 9 Mi const access to the encryption module with the key inside analysis of trilions of pairs plaintextciphertext Differential cryptanalysis of DES Biham Shamir 199 Requirements access to the encryption module with the key inside time for encryption of 247 14 1014 plaintext blocks 1 million gigabytes of plaintext Conclusions attack impossible to mount DES specially designed IBM NSA to be resistant against differential cryptanalysis 27 What if creators of DES did not know about differential cryptanalysis Required number of plaintext blocks Original DES 247 1 mln GB Modi cations Identity permutation in place ofP 219 4 MB Order of Sboxes 238 2000 GB XOR replaced by addition 231 2 GB SbOXeS random 221 16 MB one position changed 233 8 GB Expansion function E eliminated 226 64 MB Differential and linear cryptanalysis discussion Attacks infeasible for correctly designed ciphers Perfect tool for comparing strengths of various ciphers Resistance against these attacks does not imply resistance against other unknown methods of attack 28 plaintext ciphertext Triple DES EEE mode K1 encryption 56 DES encryption 56 K2 K3 encryption 56 168 bits of the key Dz ie Hellman 1977 EDE mode plaintext DES encryption K1 K2 decmption K1 encryption 112 bits of the key ciphertext Advantages Disadvantages Triple DES secure key length 112 or 168 bits increased compared to DES resistance to linear and differential cryptanalysis possibility of utilizing existing implementations of DES relatively slow especially in software 29 DE SX Rivest I988 plaintext A Kg KEY K Ka 56 DES K 120 bzts 64 Kb hash functionK Ka ciphertext ECE 646 Lecture 11 Alice s pmm key Hash functions amp MACS Digital Signature Alice Bob Mzge S39gpaulm Memga sigma fm nn I Hashvaluel HashvaluEZ I 17min key avgmun Alice 5 public key Hash function arbitrary length 1 message h hash function hash value xed length Vocabulary hash function hash value message digest message digest hash total fingerprint imprint cryptographic checksum compressed encoding MDC Message Digest Code Hash functions Basic requirements 1 Public description NO key 2 Compression arbitrary length input gt fixed length output 3 Ease of computation Hash functions Security requirements It is computationally infeasible Given To Find 1 Preimage resistance y x such that hx y 2 2nd preimage resistance x 7393 x such that xandyhx hx hx y 3 Collision resistance x 7393 x such that hx hx Hash functions Dependence between requirements 2nd preimage resistant collision resistant Hash functions unkeyed OneWay CollisionResistant Hash Functions Hash Functions OWHF CRHF preimage resistance 2nd preimage resistance collision resistance Brute force attack against OneWay Hash Function Given y i1 2 2 messages with the contents required by the forger hmi y n bits Creating multiple versions of the required message state thereby borrowed con rm that I received 10000 f Mn Kris ten thousand dollars mm Dr KrZySZtOf November 19 money 11 19 i 200839 Thls sum ofmoney should returned Mn is required to be given back to Dr Ga 27Lh N b b th da of OVem er 2006 y e 28m y Nov Gaj on Brute force attack against Yuval Collision Resistant Hash Function r messages r messages acceptable for the signer required by the forger n bits ham hmjj Message required by the forger state thereby borrowed con rm that I received 10000 f Mn Kris ten thousand dollars mm Dr KrZySZtOf November 19 money 11 19 i 200839 Thls sum ofmoney should returned Mn is required to be given back to Dr Ga 27Lh N b b th da of OVem er 2006 y e 28m y Nov Gaj on Message acceptable for the signer 1 State thereby that on Novemberlg 2008 con rm ll 19 borrowed f Mr Kris a book received mm Dr Krzysztof manuscript implementing hash functions This text factoring using Number Field Sieve item should b returned Mr G is required to 6 given back to Dr a 27m November l l of NW Birthday paradox How many students must be in a class so that there is a greater than 50 chance that I one of the students shares the teacher s birthday up to the day and month 2 any two of the students share the same birthday up to the day and month Birthday paradox How many students must be in a class so that there is a greater than 50 chance that I one of the students shares the teacher s birthday day and month 3662 188 2 any two of the students share the same birthday day and month 366 z 19 Brute force attack against Collision Resistant Hash Function Probability p that two different messages have the same hash value 2 pl exp 1 For r2 2 p63 Brute force attack against Collision Resistant Hash Function Storage requirements JJ Quisquater collision search algorithm Number of operations 2 V 752 2 2 z 25 2 2 Storage Negligible Hash value size OneWay CollisionResistant Older algorithms 11 2 64 n 2 128 8 bytes 16 bytes Current algorithms 11 Z 80 n 2 160 10 bytes 20 bytes Newly proposed algorithms 11 128192256 11 256 384 512 16 24 32 bytes 32 48 64 bytes Customized Based on Based on dedic ed block ciphers modular arithme c MIDZ C72 er1 1 m 7 141304 19334995 4 5 SHAro RIPEMD mm 1990 1 51W 1 mmmmmmgw SH anmw Mmmqm 1992 1 NSA 1995 RIPEMDrl O T T r T T 7 9A T T r NSA ZUEIEI Mr MD Hash function algorithms 15M 3mm MW smnmg 1m pamally broken culhsmns fur the cumpres Attacks against dedicated hash functions nown by 200 i l 7 W 1 51 on functl Dubbemn1996 111 hours on PC pamally broken 39 hrnkznH Dubbemn 1995 unehuur on PC 211 freebytes atthe start ufthe message reduced mund vers1 on bmken Dubbemn 1995 an What was discovered in 20042005 broken 4 Wang Feng Lai Yu Crypto 2004 manually Without using a computer 5 attack with broken 240 operations Wang Feng broken S 0 Crypto 2004 RI l al Yu2004 Wang Feng Lai Yu 1 BTW I c to 2004 xx attack W1th manully Without 11313 on a PC 263 Operations using a computer Wang M RIPEMD160 Yu Aug 2005 SHA256 SHA384 SHA512 263 operations Schneier 2005 In hardware Machine similar to the one used to break DES Cost 5000070000 Time 18 days or Cost 09l26M Time 24 hours In software Computer network similar to distributed net used to break DES 33 1252 computers Cost 0 Time 7 months Recommendations of NIST 1 NIS T Brief Comments on Recent Cryptanalytic Attacks on SHAI Feb 2005 The new attack is applicable primarily to the use of hash functions in digital signatures In many cases applications of digital signatures introduce additional context information which may make attacks impracticle Other applications of hash functions such as Message Authentication Codes MACS are not threatened by the new attacks Recommendations of NIST 2 NIST was already earlier planning to withdraw SHAl in favor of SHA224 SHA256 SHA384 amp SHA512 do roku 2010 New implementations should use new hash functions NIST encourages government agancies to develop plans for gradually moving towards new hash functions taking into account the sensitivity of the systems when setting the timetables SHA3 Contest Timeline 2007 publication of requirements 29X 2007 request for candidates 2008 31X2008 deadline for submitting candidates 2009 2 Q rst workshop devoted to the presentation of candidates 2010 2 Q second workshop devoted to the analysis of candidates 3 Q selection of nalists m last workshop selection of the winner draft version of the standard published 4 Q nal version of the standard published munn 9 90 Hash functions Applications 1 1 Digital Signatures Advantages 1 Shorter signature 2 Much faster computations 3 Larger resistance to manipulation one block instead of several blocks of signature 4 Resistance to the multiplicative attacks 5 Avoids problems with different sizes of the sender and the receiver moduli Hash functions Applications 2 2 Fingerprint of a program or a document eg to detect a modification by a Virus or an intruder fingerprint 0riginalfingerprint Hash functions Applications 3 3 Storing passwords Instead of password ID password System stores ID hashpassword hashpassword UNIX password scheme 00000000 salt salt password salt I hashpassword salt ID salt hashpassword salt salt modifies the expansion function E of DES Hash functions Applications 4 4 Fast encryption k0 hashKAB IV k1 haShKAB k0 0T kn haShKAB H km k0 hashKAB H IV k1 hashKAB H co kn haShKAB H cm General scheme for constructing a secure hash function Message In Padding appendmg b1t length M M1 IMZ Mtl I Ht hm output transformation compression function General scheme for constructing a secure hash function Compression Mi function In SHA1610 n n r512 Hi39l Hi In MDS n128 r512 Entire hash H0 IV Hi Hila Mi hm gHt Hash padding 64bits message 1000000000001 length length of the entire message in bits A11 zero padding XXXOOOOO XXXOOOOO Correct padding XXXOOIOO XXXIOOOO Parameters of dedicated hash functions speed name of h slstjalue ofjlgstzge 11039 223 relative block to MD4 MD4 128 512 3 X 16 100 MDS 128 512 4X 16 068 SHA l 160 512 4 x 20 028 RIPEMD 128 512 4 X 16 039 RIPEMD 160 160 512 5 x 16 024 Parameters of new hash functions Features affecting security and functionality SHAl SHA256 SHA384 SHA512 Size of hash 160 256 384 512 value Complexity of 280 2128 2192 2256 the best attack Equivalently secure Skipjack ABS128 ABS192 ABS256 secretkey cipher Message size lt 264 lt 264 lt 2128 lt 2128 Parameters of new hash functions Features affecting implementation speed SHAl SHA256 SHA384 SHA512 Message block 512 512 1024 1024 size Number of 80 64 80 80 digest rounds Speed Hardware implementations Conceptual comparison SHA 512 SHA 384 SHA 256 Area Results of the prototype FPGA implementation Complexity Speed in hardware Mbits GMU 2002 700 600 500 400 300 200 100 SHA l SHA 512 of the best attack 280 2256 the same as Skipjack AES256 10 years ago US Governemnt standards SHA1 Other popular hash functions MD5 RIPEMD Security status MD4 broken 1995 SHA1 replaced SHAO 1995 MD5 partially broken collisions in compression function 1996 Hash functions Present US Governemnt standards SHA1 SHA224 SHA256 SHA384 SHA512 Other popular hash functions Whirlpool winner of NESSIE Security status MD5 broken 1 hr on PC SHAO broken RIPEMD broken without a need for computer SHA1 practically broken best attack 263 operations only 128 x more than breaking DES Hash functions Timeline US Government standards IL 2003 SHA1 FlPs 180 FP3180392 SHA256 384 512 39 395 quot4V SHA224 FIPS 1802 2004 Contests 2000 XII 200 SHA256 SHA384 SHA512 NESS39E Whirlpool VIII 2004 A tEaCKS39 broken 0 MD5 collisions Vill1998 MD4 MD5 SHAO for compression SHAO atta k RIPEMD function with 251 operations 3 VH 2005 10 hrs on PC 1996 1997 1998 1999 2000 2001 2002 attack on SHA1 259a263 operacji 2003 2004 2005 2006 20 Authentication Mmge MAC Secret key Secret key M E Bah anlJce an l Bah MAC 7 Message Autentica on Codes keyed hash functions arbnrary lmgth MAC functions Basic requirements 1 Public description SECRET key parameter 2 Compression arbitrary length input gt fixed length output 3 Ease of computation MAC functions Security requirements Given zero or more pairs mi MACKmi i 1k it is computationally impossible to find any new pair m MACKm Such that 22 MAC functions Security requirements Resistance against 1 Knowntext attack 2 Chosentext attack 3 Adaptive chosentext attack CBCMAC 1 FIPS113 23 CBCMAC 1 mw H DEsKm lt9 H i 11 MACm Ht132 OI MAcltmgt EKltEKr1lt1mgt13z MAC functions CMAC h n u M k E x x a Mssmen v a MessagE engm l5 mmger mumpxe 0mm 5sz A K K a K MSBmEn T Figure 1212 QpherBased Message Authemkauon Code CMAC lb Message ength is m mtegel mulnp E 01mm 5sz RIPEMAC H0 IV 0 Hi DESKmi HM mi 1 1t MACm EKEK1Ht031 K K B 0xf0f0f0 25 HMAC Bellare Canetti Krawczyk 1996 Used in SSL and IPSec HMACm hK lt9 ipad hK lt9 opad H m ipad opad constant padding strings of the length of the message block size in the hash function h ipad repetitions of 0X36 00110110 opad repetitions of 0X5A 01011010 HMAC EB IKEY I message m American standard FIPS 198 Arbitrary hash function and key size 26 Message Authentication Codes 7 MACs ears ago U S Guvemmem standavds MAE DAC based un DES MAC DAC based un DES smce 1985 HMAC 7 based on hash lunclinns used in SSL and IPSec CMAC r Muck mphev made AES THp e DES smack AC DAC 19854993 HMAC 173wa znmw 2mg Othev MACS m use Othev MACS m use R WPEVMACS CR OMAC MAA uMAC139rMACE c MA rwmnevs uHhe NESS E contest N SSIE Winners of the contest 2002 Message Authentication Codes MACs Security level Key e Output wldth k 1 0 UC Davts 2 TTMAC U L 3 EMAC U ofToronLo 4 c NIST amp NSA ECE646 Lecture 10 RSA Implementation Ef cient encryption decryption amp key generation Efficient encryption and decryption Number of him vs number of decimal digits 10mm 2mm digim log10 2 bim z 030 bim 256 bits 384 bits 512 bits 768 bits 231 D 1024 hits 308 D 2048 hits 616 D 77D 116D 154D How to perform exponentiation efficiently YZXEmodN XXXXXXX modN Etimes E maybe u the range of 2m 10m Problems 1 huge storage necessary to store xE before reduction 2 amount of computations infeasible to perform Soluu39ons 1 modulo reduction a er eaeh multiplication 2 cleveralgorithms 200 BC Indza Chandahrs na Righttoleft binary exponentiation E my cup 1 cu L s x XImodN x4modN XgmodN x2 modN E5 en e1 92 9 eLl L Y x x2 mod N x4 mod m l x2 mod N x2 mod 10 1 W xu x Kb xeo en Ze 4e2 8ej 2 1L Y Z X modN LI 2 e 2 u X XE modN Righttoleft binary exponentiation Example 3 9 mod 11 E 19 15 2 1 100112 s x szodN x4modN XgmodN x 6 modN 3 32m0d119 92m0d114 42m0d115 52m0d113 E en e e1 e3 e4 1 1 0 0 1 Y x xlmodN 1 1 x6 modN 3 9 1 1 3 modll meodN 27m0d113 mod 1153 mod114 Lefttoright binary exponentiation Eeueueenz E 014 6L e e en vltlt 11X L ZX gtZX gtZ Z39XC YXenmodN WEN xxbxm 7 cu 2eL22eLz2 2en Y X mod N LI 7 2H eL 2 41 r 2L3 1er 2een e 2 modN x XE modN Lefttoright binary exponentiation Example Y 3 9 mod 11 E19152 1100112 E 64 e e 6 en 1 0 0 1 1 v 12 x2 1 2 12 xy x modN 32m0d11Zmod112mod1132mod113m0d11 81m0d112m0d1132m0d113m0d11 531mod113mod11 42m0d113m0d11 53m0d11 4 Y XSxyx modN meodN Exponentiation Y XE mod N Righlrmrlel t binary Leflrwrrighl binary exponenljau39on exponenljau39on Eeueueenz Exponentiation Example Y 712 mod 11 Righlrmrlel t binary Leflrwrrighl binary exponenljau39on exponenljau39on 1211002 SMquot S before round i is computed Smquot s a er round i is computed RighttoLeft Binary Exponentiation in Hardware 1 X output LefttoRight Binary Exponentiation in Hardware Basic Operations of RSA Encryption ij El public key exponent C M l mod l N ciphertm plaintm public key modulus krblts krblts krblts Decryption Lk privzm key E mm M l l c l mod l N plaintm ciphemxt krblts krblts krblts Time of exponentiation made L k modularimultiplication e L MUWODk e L modularimultiplications F3 2 z e F4 2 1 17 large random Lbit e L onese s 7 L tMWODae time ofa single modular multiplication oftwo kbit numbers modulo akbit number SOFTWARE HARDWARE MULMODk Csn 39 k2 MULMODk chm 39 k Algorithms for Modular Multiplication Multiplication 2 Multiplication combined with Paperandpew1 gag minim 39 Karatsu SchonhageStmssen FFT 9k 1nk Montgomery algorithm 6k2 Modular Reduction classical arre complexity same as multiplication used SelbyMitchell ek2 PaperiandiPencil Algorithm of Multiplication 1 Word bytes A hos A x HEM m B Assemon 2 words 2qu Brasquot In was asquot DZZAOBZA1BxA1Bn 3 words 3 wards Dz D2n6An3BnlAn2Bn2Anan3 Don Dm3AnanlAle D DmAlB l Zwuzds lecm Cnllcnlcmlc Cllcnlc Classical Algorithm 1 mfger gllZ axiom gllZ Time of basic operations in software and hardware SOF TWARE HARDWARE Modular 2 Multiplication 39 k Modular c k2L cmkL Exp ououu39au39ou W Time of the RSA operations as a function of the key size k SOFTWARE HARDWARE Enc ypu39on Signamre veri cation cs k2 ehe k with a small exponent e Deer tion yp csd k3 cm k2 Key k4l k 3 Generation csk 052 Chk 39 k 052k Factorimu39on m a expc k In kz breaking RSA 5 Effect of the increase in the computer speed on the speed of encryption and decryption in RSA CD to keep the same security encryptiondecryption speed computer operand speed siz e Decryption using Chinese Remainder Theorem mod CPCm0dP cQcmon atP dmodP1 dQ dmodQ1 El M MP RQ MQ RP mod N RP 1quot mod Q P PQquot modN RQ Q4 mod P Q Q modN

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.