RSA and Rabin.

Presentation on theme: "RSA and Rabin."— Presentation transcript:

1 RSA and Rabin

2 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公開金匙加密解密技術

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

4 Encryption using Public-Key system

5 Authentication using Public-Key System

6 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.

7 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:

8 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:

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

10 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。

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

12 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.

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

14 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

15 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)).

16 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.

17 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.

18 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.

19 Example of RSA

20 Example of RSA

21 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.

22 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}

23 Example of RSA Algorithm

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

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

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

27 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

28 RSA 參數的選擇： n的選擇

29 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

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

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

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

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

34 如何找強質數 如何找質數？是否有一簡單的公式？ 中國數學公式：若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 | 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

35 如何找強質數 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= =641* not a prime 至今並無法有一個簡單的公式找到質數

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

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

38 質數的特性

39 質數的特性

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

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

42

43 確定式質數測試法

44 Demykto 確定式產生大質數法

45 密碼學中常用的大質數有

46 Rabin PK system

47

48

49

50