Security and Weakness Shamir and zippel broken several variations of the knapsack protocols 16
16 Security and Weakness • Shamir and Zippel broken several variations of the Knapsack protocols
RSA Public Key cryptosystem The inventors R-Ron rivest s- Adi shamir Q a- Leonard adleman The One-Way Function The exponentiation function y =f(x)=x mod n can be computed with reasonable effort Its inverse x=f-(y) is extremely difficult to compute The Hard Problem Securing the Trapdoor The rsa public key algorithm is based on the well- known hard problem of factoring large numbers into its prime factors that has been studied over many centuries 17
17 RSA Public Key Cryptosystem • The Inventors – R - Ron Rivest – S - Adi Shamir – A - Leonard Adleman • The One-Way Function – The exponentiation function y = f(x) = xe mod n can be computed with reasonable effort. – Its inverse x = f -1 (y) is extremely difficult to compute. • The Hard Problem Securing the Trapdoor – The RSA public key algorithm is based on the wellknown hard problem of factoring large numbers into its prime factors that has been studied over many centuries
X*X JPEG image 2142x1504 pixels-Netscape File Edit View Go Communicator Help At Crypto 82 Search Netscape Print f"Bookmarks J Location: htp:./, Ics. mit.edu/X7Erivest/Len-Ad-Ron,ipg ICP"What's Related 目立」
18 At Crypto 82
点23.品,,a岛 E Bookmarks Location: htp:/theory. Ics. mi. edu/x7Erivest/rsa-photo ipeg Eo"what's Related P=NP 目。」
19
Key generation Algorithm Step 1: Choose two random large prime numbers p and q For maximum security, choose p and g of about equal length e.g. 512-1024 bits each Step 2: Compute the product=pq Step 3: Choose a random integer e<(p-1)(q-1)(n=(p-1)(q-1) The numbers e and(p-1)(q-1)must be relatively prime, i. e. they should not share common prime factors Step 4: Compute the unique inverse d=e-l mod(p-1)(q-1) The equation d'e mod(p-1)(q-1) can be solved using the euclidian algorithm 20
20 Key Generation Algorithm • Step 1: Choose two random large prime numbers p and q – For maximum security, choose p and q of about equal length, e.g. 512-1024 bits each. • Step 2: Compute the product n = p·q • Step 3: Choose a random integer e < (p-1)(q-1) (n)= (p-1)(q-1) – The numbers e and (p-1)(q-1)must be relatively prime, i.e. they should not share common prime factors. • Step 4: Compute the unique inverse d = e-1 mod (p-1)(q-1) – The equation d·e mod (p-1)(q-1) = 1 can be solved using the Euclidian algorithm