RSA and Rabin

Introduction Diffie and Hellman 提出單向暗門函數的公開金匙密碼系統。但不確定one-way function 是否存在。 Pohlig and Hellman published an encryption scheme based on computing exponentials over a finite field. 1978 MIT Rivest，Shamir，Adleman (RSA）提出 以分解因數的指數函數為基礎的one-way function 具有可逆性及交換性。 RSA公開金匙加密解密技術

數學基礎複習 單向函數（One-way function）：由g及x求y=Fx(g)容易，由g及y求x，於計算上不可能。 交換性：Fx1(Fx2(g))=Fx2(Fx1(g)) 可逆性：Fx-1(Fx(g))=g。

Encryption using Public-Key system

Authentication using Public-Key System

Applications for Public-Key Cryptosystems Three categories: Encryption/decryption: The sender encrypts a message with the recipient’s public key. Digital signature: The sender ”signs” a message with its private key. Key echange: Two sides cooperate two exhange a session key.

Requirements for Public-Key Cryptography Computationally easy for a party B to generate a pair (public key KUb, private key KRb) Easy for sender to generate ciphertext: Easy for the receiver to decrypt ciphertect using private key:

Requirements for Public-Key Cryptography Computationally infeasible to determine private key (KRb) knowing public key (KUb) Computationally infeasible to recover message M, knowing KUb and ciphertext C Either of the two keys can be used for encryption, with the other used for decryption:

Introduction In Scientific American，the RSA scheme as “A New Kind of Cipher That Would Take Millions of Years to Break”

Basic Idea The Pohlig-Hellman and RSA shcemes both encipher a message block M in [0, n-1] by computing the exponential： C = Me mod n, where e and n are the key to the enciphering transformation. M is restored by the same operation, but using a different exponent d for the key： M = Cd mod n。

Basic Idea Enciphering and deciphering can be implemented using the fast exponentiation algorithm. C=fastexp(M,e,n) M=fastexp(C,d,n)

Basic Idea Note: gcd(M,n)=1，Mø(n) mod n=1 This property implies that if e and d satisfy the relation ed mod ø(n) =1, then M = Cd mod n is the inverse of C = Me mod n。 Theorem Given e and d satisfying Eq. (2.4) and a message M in [0,n-1] such that gcd(M,n)=1, (Me mod n)d mod n=M.

Proof of Theorem (Me mod n)d mod n=M

Basic Idea By symmetry, enciphering and deciphering are communicative and mutual inverses, thus (Md mod n)e mod n=Mde mod n=M. It is because of this that the RSA scheme can be used for secrecy and authenticity in a public-key system

Basic Idea Given ø(n)，it is easy to generate a pair (e,d) satisfying ed mod ø(n)=1, First choosing d relatively prime to ø(n), and then using the extended version of Euclid’s algorithm to compute its inverse: e = inv (d, ø(n)). Note: pick e and compute d =inv (e, ø(n)).

Pohlig-Hellman Scheme The modulus is chosen to be a large prime p. The enciphering and deciphering are thus given by C= Me mod p M =Cd mod p where all arithmetic is done in the Galois field GF(p). Because p is prime, ø(p)=p-1.

Example of P-H Scheme Let p =11, whence ø(p)=p-1=10. Choose d =7 and compute e = inv(7,10)=3. Suppose M =5. Then M is enciphered as: C= Me mod p= 53 mod 11 =4. C is deciphered as M =Cd mod p=47 mod 11=5.

RSA scheme In the RSA scheme, the modulus n is the product of two large primes p and q: n=pq Thus ø(n)=(p-1)(q-1) Encipher: C = Me mod n, Decipher: M = Cd mod n。 Recommend that picked d relatively prime to ø(n) in the interval [max(p,q)+1, n-1] e = inv (d, ø(n)). In inv (d, ø(n)) returns e such that e < log2n, then a new value of d should be picked to ensure that every encrypted message undergoes some wrap-around.

Example of RSA

Example of RSA

RSA Because ø(n) cannot be determined without knowing the prime factors p and q, it is possible to keep d secret even if e and n are made public. The security of the system dependes on the difficulty of factoring n into p and q. The fastest known factoring algorithm takes T=exp(sqrt (ln n ln ln n)) steps. RSA suggest that: p and q are 100-digit numbers; then n is 200.

The RSA Algorithm – Key Generation Select p,q p and q both prime Calculate n = p x q Calculate Select integer e Calculate d Public Key KU = {e,n} Private key KR = {d,n}

Example of RSA Algorithm

The RSA Algorithm - Encryption Plaintext: M<n Ciphertext: C = Me (mod n)

The RSA Algorithm - Decryption Ciphertext: C Plaintext: M = Cd (mod n)

RSA 參數的選擇 不論m是否與n互質，在RSA系統中均可解密還原m。 若m不與n互質，則m與n之最大公因數不是p就是q，易遭破解。

RSA 參數的選擇： n的選擇 p與q必須為強質樹（strong prime） Strong Prime: 若一質數滿足下列條件，則為強質數 存在兩個大質數p1 and p2，使的p1 |p-1 and p2| p+1。 存在四個大質數r1,s1,r2及s2使的r1|p1-1, s1|p1+1, r2|p2-1, s2|p2+1

RSA 參數的選擇： n的選擇

RSA 參數的選擇： n的選擇 p及q的差必須很大 若p與q的差很小； 估計p及q的平均值(p+q)/2為N1/2 ， Eg. N=164009, (p+q)/2=405, 4052-N=16=42 (p+q)/2=405, (p-q)/2=4，=> p=409, q=401

RSA 參數的選擇： n的選擇 p-1與q-1的gcd要很小，

RSA 參數的選擇： n的選擇 p及q的必須很大到要分解n不可能 分解x+10位數的困難度，大約是分解x位數的十倍 分解140位數的困難度，大約是分解130位數的十倍

RSA 參數的選擇： e的選擇 有學者建議設定e=3，BUT

RSA 參數的選擇： d的選擇 於ic卡的應用中，因運算速度慢，故要key d 的長度小一些，但易被破解。

如何找強質數 如何找質數？是否有一簡單的公式？ 中國數學公式：若n整除2n-2，n為質數。 eg. n=3, 23-2=6, 3|6, 3 is prime n < 341 is ok n =341 =11 * 31, but 341 | 2341-2 Mersenne推測：if p is prime then Mp=2p-1 is prime eg. p=2, M2=22-1=3 p=3, M3=23-1 =7 but p=11, M11=211-1=2047=23*89 not a prime

如何找強質數 Fermat 定理：若Fn=22n+1，then n is prime Proof: n <5 is true, n=0, F0=3, n=1, F1=5, n=2, F2=17, n=3, F3=257, n=4, F4=65537 are primes. But n=5, F5=4294967297=641*6700417 not a prime 至今並無法有一個簡單的公式找到質數

質數的特性 質數的分佈極不規則 質數越大則分布的越稀疏 質數的個數有無窮多個

質數的特性 給定一個數x，比x小的質數有多少個？

質數的特性

質數的特性

大質數的產生 機率式質數測試法

大質數的產生 機率式質數測試法

確定式質數測試法

Demykto 確定式產生大質數法

密碼學中常用的大質數有

Rabin PK system