Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Topic 1: Trial Division Sieve (1)Topic 1: Trial Division Sieve (2)Topic 1: Trial Division Sieve (3)Topic 1: Trial Division Sieve (4)Slide 16Topic 2: Greatest Common Divisor and Multiplicative Inverse(2)Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48p-1 algorithmp-1 algorithm – Phase 1p-1 Phase 1 – Numerical exampleSlide 52Slide 53Slide 54Structure of a Typical Digital SystemHardware Design with RTL VHDLSteps of the Design ProcessProject 2 - Platform & toolsSlide 59Slide 60Slide 61Slide 62Slide 63Slide 64Slide 65Design FlowHandel-C / ANSI-C ComparisonsHandel-C Language (1)Handel-C Language (2)Handel-C Language (3)Platform & tools – HLL CompilersVHDL macro declaration in Handel-CSlide 73Slide 74LiteratureProject OrganizationECE 645Spring 2007PROJECT 2SpecificationTopic OptionsPublic Key (Asymmetric) CryptosystemsPublic key of Bob - KBPrivate key of Bob - kBAliceBobNetworkEncryptionDecryptionRSA as a trap-door one-way functionMC = f(M) = Me mod NCM = f-1(C) = Cd mod NPUBLIC KEYPRIVATE KEYN = P  QP, Q - large prime numberse  d  1 mod ((P-1)(Q-1))RSA keysPUBLIC KEYPRIVATE KEY{ e, N }{ d, P, Q }N = P  Qe  d  1 mod ((P-1)(Q-1))P, Q - large prime numbersEarly Factoring Device – Lehmer SieveBicycle chain sieve [D. H. Lehmer, 1928]Computer Museum, Mountain View, CASupercomputer Cray-1 from 1980’sComputer Museum, Mountain View, CAFPGA based supercomputersMachineReleasedSRC 6 fromSRC ComputersCray XD1 fromfrom CraySGI Altix fromSGISRC 7 fromSRC Computers, Inc,2002200520052006Ruhr University, Bochum, University of Kiel, Germany, 2006120 Spartan 3 FPGAsClock frequency 100 MHzCost: € 8980COPACOBANAFactoring 1024-bit RSA keysusing Number Field Sieve (NFS) Polynomial Selection Linear AlgebraSquare Root Relation Collection Sieving Cofactoring 200 bit numbers & 350 bitTrial divisionECM, p-1 method, rho methodTopic 1Trial Division SieveTopic 1: Trial Division Sieve (1)Given: Inputs:Variables:1. Integers N1, N2, N3, .... each of the size of k-bitsConstants:2. Factor base = set of all primes smaller smaller than a certain bound B = { p1=2, p2=3, p3=5, ... , pt ≤ B }Parameters of interest: 4 ≤ k ≤ 512 3 ≤ B ≤ 105Topic 1: Trial Division Sieve (2)Required: Outputs:For each integer Ni:A list of primes from the factor base that divides Ni, and the number of times each prime divides Ni.For example if Ni = p1e1 · p2e2 · p3e3 · Mi, where Mi is not divisible by any prime belonging to a factor base, thenthe output is {p1, e1}, {p2, e2}, {p3, e3}Topic 1: Trial Division Sieve (3)Example:Constants:k=10, B=5Factor base = {2, 3, 5}Variables: N1 = 408 = 23 · 3 · 17 N2 = 630 = 2 · 32 · 5 · 7Outputs: {2, 3}, {3, 1} {2, 1}, {3, 2}, {5, 1}Topic 1: Trial Division Sieve (4)Optimization Criteria: Maximum number of integers Ni fully processed per unitof time for a given k and B.Topic 2Greatest Common Divisor&Multiplicative InverseTopic 2: Greatest Common Divisor and Multiplicative Inverse(2)Given: Inputs: a, N: k-bit integers; a < NOutputs: y = gcd(a, N) x = a-1 mod N i.e., integer 1 ≤ x < N, such that a  x (mod N) = 1Parameters of interest: 4 ≤ k ≤ 1024Greatest common divisorGreatest common divisor of a and b, denoted by gcd(a, b),is the largest positive integer that divides both a and b.d = gcd (a, b) iff 1) d | a and d | b 2) if c | a and c | b then c  dgcd (8, 44) =gcd (-15, 65) =gcd (45, 30) =gcd (31, 15) =gcd (121, 169) =Quotient and remainderGiven integers a and n, n>0! q, r  Z such that a = q n + r and 0  r < nq – quotientr – remainder (of a divided by n) q = an= a div nr = a - q n = a – an n== a mod nEuclid’s Algorithmfor computing gcd(a,b)i-2-1 0 1…t-1 trir-2 = max(a, b)r-1 = min(a, b)r0r1…rt-1 = gcd(a, b)rt=0qiq-1q0q1…qt-1 qi = ri-1riri+1 = ri-1 - qi  riri+1 = ri-1 mod riEuclid’s AlgorithmExample: gcd(36, 126)i-2-1 0 1rir-2 = max(a, b) =126r-1 = min(a, b) =36r0 = 18 = gcd(36, 126)r1 = 0qiq-1 = 3q0 = 2q1qi = ri-1riri+1 = ri-1 - qi  riri+1 = ri-1 mod riMultiplicative inverse modulo nThe multiplicative inverse of a modulo n is an integer [!!!]x such that a  x  1 (mod n)The multiplicative inverse of a modulo n is denoted bya-1 mod n (in some books a or a*).According to this notation: a  a-1  1 (mod n)Extended Euclid’s Algorithm (1)i-2-1 0 1…t-1 trir-2 = nr-1 = ar0r1…rt-1 rt=0xix-2=0x-1=1x0x1…xt-1xtqiq-1 =  n/a q0q1…qt-1 qi = ri-1riri+1 = ri-1 - qi  rixi+1 = xi-1 - qi  xiyi+1 = yi-1 - qi  yiyiy-2=1y-1=0y0y1…yt-1ytri = xi  a + yi  nrt-1 = xt-1  a + yt-1  nExtended Euclid’s Algorithm (2)rt-1 = xt-1  a + yt-1  nrt-1 = xt-1  a + yt-1  n  xt-1  a (mod n) If rt-1 = gcd (a, n) = 1 then xt-1  a  1 (mod n)and as a result xt-1 = a-1 mod nExtended Euclid’s Algorithmfor computing z = a-1 mod ni-2-1 0 1…t-1 trir-2 = nr-1 = ar0r1…rt-1 = 1rt=0xix-2=0x-1=1x0x1…xt-1 = a-1 mod nxt = nqiq-1 =  n/a q0q1…qt-1 qi = ri-1riri+1 = ri-1 - qi  rixi+1 = xi-1 - qi  xiIf rt-1  1 the inverse does not existNote:Extended Euclid’s AlgorithmExample z = 20-1 mod 117i-2-1 0 1 2 3 4rir-2 = 117r-1 = 20r0 = 17r1 = 3r2 = 2r3 = 1r4 = 0xix-2= 0x-1= 1x0 =-5x1 = 6x2 = -35x3 = 41 = 20-1 mod 117x4 = -117qiq-1 = 5q0 = 1q1 = 5 q2 = 1q3 = 2qi = ri-1riri+1 = ri-1 - qi  rixi+1 = xi-1 - qi  xiCheck:20  41 mod 117 = 1Topic 3RSA Encryption & DecryptionwithMontgomery Multipliers based on Carry Save AddersRSA as a trap-door one-way functionMC = f(M) = Me mod NCM = f-1(C) = Cd mod NPUBLIC KEYPRIVATE KEYN = P  QP, Q - large prime numberse  d  1 mod ((P-1)(Q-1))Right-to-left binary exponentiationLeft-to-right binary exponentiationExponentiation: Y = XE mod NE = (eL-1, eL-2, …, e1, e0)2Y = 1;S = X;for i=0 to L-1 { if (ei == 1) Y = Y  S mod N; S = S2 mod N; }Y = 1;for i=L-1 downto 0 { Y = Y2 mod N; if (ei == 1) Y = Y  X mod N; }Montgomery Modular Multiplication (1)C = A  B mod MAInteger domainMontgomery domainA’ = A  2k mod MBB’ = B  2k mod MC’ = MP(A’,