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 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
JPEG image 2142x1504 pixels-Netscape File Edit View Go Communicator Help At Crypto 82 3a应的翟 Back Forward Reload Home Search Netscape Print Security Shop Stop E"Bookmarks J Location (htp:l/theoy les mi edu/.7TEnivest/Len Ad -Ronipg ("what's Related 目的
18 At Crypto 82
*JPEG image 1039x754 pixels-Netscape File Edit View Go Communicator Help Back Forward Reload Home Search Netscape Print Security Shop Stop what's Related 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|n=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-mod(p-1(q-1) The equation d e mod(p-1)(q can be solved using the euclidian algorithm
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