iT邦幫忙

2

RSA公開金鑰加密的數學知識

rsa
  • 分享至 

  • xImage
  •  

時鐘加法

指針指向9
前進 6 格之後,會指向哪裡?

9 + 6 = 15

但是,時鐘上沒有15這個數字。
結果:指向 3

(9 + 6) % 12 = 3


時鐘乘法

5 x 3  指針會指向哪裡?
乘法就是「重複做加法」、每次加一樣的數字

(5 + 5 + 5) % 12 = 3
(5 * 3) % 12 = 3


時鐘乘法(大數字)

121 x 125 指針會指向哪裡呢?
有兩種算法

  1. 直接用乘法
      (121 * 125) % 12 = 5

  2. 各自取餘數 → 餘數互乘 → 再取餘數
      (121 % 12) * (125 % 12) % 12 = 5

  指針指向121,相當於指向 (121 % 12)這個數字
  從起點前進125次,相當於前進 (125 % 12)次


時鐘乘法(負數)

-1 x 3 指針會指向哪裡呢?

-1 就是:數字12 往後退 1 步的那個數字,
12 + (-1) = 11

-1 * 3 相當於 (11 * 3) % 12 = 9

====================
-1 * 3 = -3

-3 就是:數字12 往後退 3 步的那個數字,
12 + (-3) = 9

-1 x -3 指針會指向哪裡呢?

-1 就是:數字12 往後退 1 步的那個數字,
  12 + (-1) = 11

-3 就是:移動 9 次
  12 + (-3) = 9
  in [時鐘size 12] , 移動 9 次 = 移動 (9 + 12)次 = 移動 (9 + 2*12)次
            移動 9 次 = 移動 (9 - 12)次 = 移動 (9 - 2*12)次

-1 * -3 相當於 11 * 9
(11 * 9) % 12 = 3

-1 * -3 = 3


時鐘次方

https://chart.googleapis.com/chart?cht=tx&chl=%242%5E5%24指針會指向哪裡?

次方就是「重複做乘法」,每次都乘一樣的數字
(2 * 2 * 2 * 2 * 2) % 12 = 8

https://chart.googleapis.com/chart?cht=tx&chl=%24(7%5E2)%5E%7B25%7D%24指針會指向哪裡?

有五種算法:

  1. 先計算小括弧裡面
      https://chart.googleapis.com/chart?cht=tx&chl=%24(7%5E2)%5E%7B25%7D%24 = https://chart.googleapis.com/chart?cht=tx&chl=%24%7B49%7D%5E%7B25%7D%24 然後除以12,取餘數

  2. 先把指數相乘
      https://chart.googleapis.com/chart?cht=tx&chl=%24(7%5E2)%5E%7B25%7D%24 = https://chart.googleapis.com/chart?cht=tx&chl=%247%5E%7B50%7D%24   然後除以12,取餘數

  3. 先把(https://chart.googleapis.com/chart?cht=tx&chl=%247%5E2%24)的餘數算出來
      https://chart.googleapis.com/chart?cht=tx&chl=%24(7%5E2)%5E%7B25%7D%24  →  https://chart.googleapis.com/chart?cht=tx&chl=%24%7B49%7D%5E%7B25%7D%24 →  https://chart.googleapis.com/chart?cht=tx&chl=%24(49%20%25%2012)%5E%7B25%7D%24 → https://chart.googleapis.com/chart?cht=tx&chl=%24(1)%5E%7B25%7D%24 → 1

  4. 規律:
      數字7 in [時鐘size 12]
        次方 1 2 3 4 5 6
        餘數 7 1 7 1 7 1

  7的奇數次方(1、3、5、…)在[時鐘size 12]會指向 7
  7的偶數次方(2、4、6、…)在[時鐘size 12]會指向 1
  所以,https://chart.googleapis.com/chart?cht=tx&chl=%24(7%5E2)%5E%7B25%7D%24在[時鐘size 12]會指向 1

  1. 根據https://chart.googleapis.com/chart?cht=tx&chl=%247%5En%24的餘數
      如果知道 https://chart.googleapis.com/chart?cht=tx&chl=%247%5E%7B49%7D%24的餘數是 7
      那麼,https://chart.googleapis.com/chart?cht=tx&chl=%247%5E%7B50%7D%24的餘數,就是 7 * (7) % 12

  如果知道 https://chart.googleapis.com/chart?cht=tx&chl=%247%5E%7B48%7D%24的餘數是 1
  那麼,https://chart.googleapis.com/chart?cht=tx&chl=%247%5E%7B50%7D%24的餘數,就是 1 * (7 * 7) % 12


時鐘乘法 - 只會指向那些數字

時鐘size 12 的質因數分解 = https://chart.googleapis.com/chart?cht=tx&chl=%242%5E2*3%24

時鐘上的數字分成兩類:
  和 12的因數「部份相同」or「完全相同」:2、3、4、6、8、9、10、12
    2 乘以某數 → 2的倍數(2、4、6、8、10、12)
    3 乘以某數 → 3的倍數(3、6、9、12)
    4 乘以某數 → 4的倍數(4、8、12)
    6 乘以某數 → 6的倍數(6、12)
    8 乘以某數 → 4的倍數(4、8、12)       (注意這裡)
    9 乘以某數 → 3的倍數(3、6、9、12)      (注意這裡)
    10乘以某數 → 2的倍數(2、4、6、8、10、12)   (注意這裡)
    12乘以某數 → 12的倍數(12)

    指向的數字,是它和 12 的「最大公因數」的倍數
    不會指向數字 1

  和 12的因數「完全不同」(除了 因數1 之外)(互質):1、5、7、11
    1 乘以某數 → 所有數字
    5 乘以某數 → 所有數字
    7 乘以某數 → 所有數字
    11乘以某數 → 所有數字

    「與時鐘size 互質之數」x 「與時鐘size 互質之數」
    有機會指向數字 1


最大公因數

用「因數」來組成數字

  8 = 1 x 8 = 2 x 4
  8的因數是 1、2、4、8

  12 = 1 x 12 = 2 x 6 = 3 x 4
  12的因數是 1、2、3、4、6、12

最大公因數:兩個數字的「最大」「相同」「因數」

  8 和 12 的最大公因數:4

如何知道「最大公因數」是哪一個數字

方法 1:
  把 8 和 12 的因數都列出來,
  找「最大」「相同」的那一個

方法 2:
  理解 8 和 12 可以用 「最大公因數 4」 組成
  8 和 12 的「差」,也可以用「最大公因數 4」 組成

    8 = 4 x 2
    12 = 4 x 3
  
    12 - 8 = 4
        = 4 x 1


輾轉相除法(歐幾里得算法) - 使用除法

求 130 和 30 的最大公因數

130 - 30 = 100
與其找「130 和 30 的最大公因數」,不如找「100 和 30 的最大公因數」

100 - 30 = 70
與其找「100 和 30 的最大公因數」,不如找「70 和 30 的最大公因數」

70 - 30 = 40
與其找「70 和 30 的最大公因數」,不如找「40 和 30 的最大公因數」

40 - 30 = 10
與其找「40 和 30 的最大公因數」,不如找「30 和 10 的最大公因數」

用減法有點慢。直接用除法
130 % 30 = 10
與其找「130 和 30 的最大公因數」,不如找「30 和 10 的最大公因數」
  


輾轉相除法(歐幾里得算法)的例子

a = 240
b = 46

240 % 46 = 10
46 % 10 = 6
10 % 6 = 4
6 % 4 = 2
4 % 2 = 0
當餘數為 0,除數 2 就是240 和 46 的最大公因數

觀察上面式子,可以發現:
  餘數:向左進化成「除數」
  除數:向左進化成「被除數」


擴展歐幾里得算法

原本的被除數240、除數46也是「餘數」
所以,可以寫成以下式子

L % M = 240
  與其找「L 和 M 的最大公因數」,不如找「M 和 240 的最大公因數」

M % 240 = 46
  與其找「M 和 240 的最大公因數」,不如找「240 和 46 的最大公因數」

240 % 46 = 10
46 % 10 = 6
10 % 6 = 4
6 % 4 = 2
4 % 2 = 0

=================================
每代餘數都可以表示成:
  240*s + 46*t = 餘數
  240的幾倍 + 46的幾倍 = 餘數

1代餘數:  240*1 + 46*0 = 240 → 240*https://chart.googleapis.com/chart?cht=tx&chl=%24s_1%24 + 46*https://chart.googleapis.com/chart?cht=tx&chl=%24t_1%24 = 240
2代餘數:  240*0 + 46*1 = 46  → 240*https://chart.googleapis.com/chart?cht=tx&chl=%24s_2%24 + 46*https://chart.googleapis.com/chart?cht=tx&chl=%24t_2%24 = 46

    https://chart.googleapis.com/chart?cht=tx&chl=%24q_3%24https://chart.googleapis.com/chart?cht=tx&chl=%24q_7%24代表「商」(負數)
3代餘數:  240 + https://chart.googleapis.com/chart?cht=tx&chl=%24q_3%24*46 = 10  → (1代餘數) + https://chart.googleapis.com/chart?cht=tx&chl=%24q_3%24*(2代餘數) = 10
                    ↓ 穢土轉生

                (240*https://chart.googleapis.com/chart?cht=tx&chl=%24s_1%24 + 46*https://chart.googleapis.com/chart?cht=tx&chl=%24t_1%24) + https://chart.googleapis.com/chart?cht=tx&chl=%24q_3%24*(240*https://chart.googleapis.com/chart?cht=tx&chl=%24s_2%24 + 46*https://chart.googleapis.com/chart?cht=tx&chl=%24t_2%24) = 10
                240*(https://chart.googleapis.com/chart?cht=tx&chl=%24s_1%24 + https://chart.googleapis.com/chart?cht=tx&chl=%24q_3%24*https://chart.googleapis.com/chart?cht=tx&chl=%24s_2%24) + 46*(https://chart.googleapis.com/chart?cht=tx&chl=%24t_1%24 + https://chart.googleapis.com/chart?cht=tx&chl=%24q_3%24*https://chart.googleapis.com/chart?cht=tx&chl=%24t_2%24) = 10
                    ↓
                240*https://chart.googleapis.com/chart?cht=tx&chl=%24s_3%24 + 46*https://chart.googleapis.com/chart?cht=tx&chl=%24t_3%24 = 10
                  (https://chart.googleapis.com/chart?cht=tx&chl=%24s_3%24 可以用 https://chart.googleapis.com/chart?cht=tx&chl=%24s_1%24 https://chart.googleapis.com/chart?cht=tx&chl=%24s_2%24 https://chart.googleapis.com/chart?cht=tx&chl=%24q_3%24 計算出來)

4代餘數:  46 + https://chart.googleapis.com/chart?cht=tx&chl=%24q_4%24*10 = 6   → (2代餘數) + https://chart.googleapis.com/chart?cht=tx&chl=%24q_4%24*(3代餘數) = 6
5代餘數:  10 + https://chart.googleapis.com/chart?cht=tx&chl=%24q_5%24*6 = 4   → (3代餘數) + https://chart.googleapis.com/chart?cht=tx&chl=%24q_5%24*(4代餘數) = 4
6代餘數:  6 + https://chart.googleapis.com/chart?cht=tx&chl=%24q_6%24*4 = 2   → (4代餘數) + https://chart.googleapis.com/chart?cht=tx&chl=%24q_6%24*(5代餘數) = 2
7代餘數:  4 + https://chart.googleapis.com/chart?cht=tx&chl=%24q_7%24*2 = 0   → (5代餘數) + https://chart.googleapis.com/chart?cht=tx&chl=%24q_7%24*(6代餘數) = 0

最後會得到:
  240*(-9) + 46*(47) = 2
  「240的幾倍」+「46的幾倍」= 最大公因數

意思(1):
  46 是[時鐘 size 240]上的一個數字
  「前進」 47 次(總共轉了 9 圈)
  最後指向「數字 2」

  or
  240 是[時鐘 size 46]上的一個數字
  「後退」 9 次(接近 47 圈)
  最後指向「數字 2」

意思(2):
  倍數有多組解

  240*(-9)    + 46*(47)     = 2
  240*(-9 + 46)  + 46*(47 - 240)  = 2
  240*(-9 - 46)  + 46*(47 + 240)  = 2
  240*(-9 - 46*n) + 46*(47 + 240*n) = 2
    加號左邊:減掉 240*46*n
    加號右邊:加上 240*46*n

  240*(-9 - 46/2*n) + 46*(47 + 240/2*n) = 2
    加號左邊:減掉 (240*46/2)*n
    加號右邊:加上 (240*46/2)*n
      最大公因數 = 2
      最小公倍數 = 240*46/2

意思(3):
  46 和 47是[時鐘 size 240]上的兩個數字
  相乘之後,指向 2
  (46 + 240*幾倍) * (47 + 240*幾倍) 也會指向 2

  240 和 -9 是 [時鐘 size 46]上的兩個數字
  相乘之後,指向 2
  (240 + 46*幾倍) * (-9 + 46*幾倍) 也會指向 2


時鐘次方 - 會不會指回原本的數字

和 12的因數「部份相同」:2、3、4、6、8、9、10
       1  2  3  4  5 (次方)
  --------------------------------------------
    2  2  4  8  4  8  (不能指回原本的數字)
    3  3  9  3  9  3
    4  4  4  4  4  4
    6  6  0  0  0  0  (不能指回原本的數字)
    8  8  4  8  4  8
    9  9  9  9  9  9
    10  10  4  4  4  4  (不能指回原本的數字)
    有的可以指回原本的數字,有的不行

  
和 12的因數「完全不同」(除了 因數1 之外)(互質):1、5、7、11
       1  2  3  4  5 (次方)
  -----------------------------------------------
    1  1  1  1  1  1
    5  5  1  5  1  5
    7  7  1  7  1  7
    11  11  1 11  1 11
    全部都可以指回原本的數字
    指回原本的數字之前,會先指向 1
      n次方是 1
      n+1次方 = 1 x 原數字 = 原數字

    對5、7、11來說:
      「首先」在2次方指向 1
      所以,週期就是 2
      
      意思是:
        0 次方 = 2 次方 = 2n次方 = 1
        1 次方 = (1+2)次方 = (1 + 2n)次方 = 原本的數字


質數時鐘 - 指回原本數字的週期

  [時鐘size 19]:
    因為是質數時鐘,數字 1 ~ 18 都和時鐘size 19 互質,
    在進行時鐘次方後,都會指回原本的數字

  幾個數字的時鐘次方
                                  (次方)
  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18
  ---------------------------------------------------------------------------------------------
2  2  4  8 16 13  7 14  9 18  17 15 11  3  6 12  5 10  1
                 (18相當於 -1)

6  6 17  7  4  5 11  9 16  1
7  7 11  1
18 18  1
  (18相當於-1)

  2的週期 = 18
  6的週期 = 9
  7的週期 = 3
  18的週期 = 2

  每個數字的「個別週期」有的較長、有的較短
  它們的共同點是:
    「個別週期」的某倍,等於「共同週期」
    「個別週期」會指向 1
    「共同週期」也會指向 1

  質數時鐘的「共同週期」= 時鐘size - 1


質數時鐘 - 週期的組成

  質數時鐘 size p
  時鐘上的數字 a

「a等於p」 和 「a小於p」 的差別

  共同點:
    https://chart.googleapis.com/chart?cht=tx&chl=%24a%5Ep%24 指向 a

  不同點:
    a等於p:https://chart.googleapis.com/chart?cht=tx&chl=%24a%5E%7Bp-1%7D%24 指向 a

    a小於p:https://chart.googleapis.com/chart?cht=tx&chl=%24a%5E%7Bp-1%7D%24 指向 1

https://chart.googleapis.com/chart?cht=tx&chl=%24a%5E2%24 會不會指向 a ? 大部份的數字不會

  (只有 a=1 或 a=p https://chart.googleapis.com/chart?cht=tx&chl=%24a%5E2%24 會指向 a)

  如果https://chart.googleapis.com/chart?cht=tx&chl=%24a%5E2%24會指向 a
  表示:
    a的1倍 到 a的a倍
    從位置 a ,轉了n圈之後,又回到原來的位置a
    https://chart.googleapis.com/chart?cht=tx&chl=%24a%5E2%24 - a = p的倍數

  對大部份的數字而言,
  https://chart.googleapis.com/chart?cht=tx&chl=%24a%5E2%24 - a = a x (a - 1)
  a 和 (a - 1) 都和 p 互質
  所以,https://chart.googleapis.com/chart?cht=tx&chl=%24a%5E2%24 不會指向 a
  =============================================
  以上是質數時鐘的情形
  然而,在合成數時鐘 [時鐘size 12]
  https://chart.googleapis.com/chart?cht=tx&chl=%249%5E2%24指向 9
  https://chart.googleapis.com/chart?cht=tx&chl=%249%5E2%24 - 9 = 12的倍數

  https://chart.googleapis.com/chart?cht=tx&chl=%249%5E2%24 - 9 = 9 x (9 - 1)
  9 和 8 沒有和 [時鐘size 12] 互質、有大於1的相同因數
  9 x 8 等於 12的倍數

https://chart.googleapis.com/chart?cht=tx&chl=%24a%5E2%24 會不會指向 1 ? 只有 a=1 和 a=-1會

  當 https://chart.googleapis.com/chart?cht=tx&chl=%24a%5E2%24指向 1
  表示:https://chart.googleapis.com/chart?cht=tx&chl=%24a%5E2%24 - 1 = p的倍數
    (a+1)(a-1) = p的倍數
    a的「前面數字」 x a的「後面數字」 = p的倍數
    (前面數字 = p 或 後面數字 = p)
  
  1 和 (-1) 的前面 or 後面
  有一個數字是 p
  所以,https://chart.googleapis.com/chart?cht=tx&chl=%241%5E2%24https://chart.googleapis.com/chart?cht=tx&chl=%24(-1)%5E2%24會指向 1
  
  其他數字的隔壁數字:
    不會是 p
    和 p 互質、沒有大於1的相同因數
  所以(其他數字)^2不會指向 1

  =============================================
  以上是質數時鐘的情形
  然而,在合成數時鐘 [時鐘size 12]
  https://chart.googleapis.com/chart?cht=tx&chl=%245%5E2%24指向 1
  https://chart.googleapis.com/chart?cht=tx&chl=%247%5E2%24指向 1

  5的的隔壁數字 4 和 6
    沒有和 [時鐘size 12]互質
    有大於1的相同因數
    4 x 6 = 12 的倍數

  7的的隔壁數字 6 和 8
    沒有和 [時鐘size 12]互質
    有大於1的相同因數
    6 x 8 = 12 的倍數
  

https://chart.googleapis.com/chart?cht=tx&chl=%24a%5E3%24指向 1 的情形

  https://chart.googleapis.com/chart?cht=tx&chl=%24a%5E3%24不一定會指向 1 ,要根據時鐘size而定
  
  以下是 [時鐘size 19] 的例子
  https://chart.googleapis.com/chart?cht=tx&chl=%247%5E3%24 = https://chart.googleapis.com/chart?cht=tx&chl=%247%5E2%24 x 7
    = 11 x 7 (指向 1)

https://chart.googleapis.com/chart?cht=tx&chl=%24a%5E9%24指向 1 的情形

  https://chart.googleapis.com/chart?cht=tx&chl=%24a%5E9%24不一定會指向 1 ,要根據時鐘size而定
  
  以下是 [時鐘size 19] 的例子
  https://chart.googleapis.com/chart?cht=tx&chl=%246%5E9%24 = https://chart.googleapis.com/chart?cht=tx&chl=%246%5E3%24 x https://chart.googleapis.com/chart?cht=tx&chl=%246%5E3%24 x https://chart.googleapis.com/chart?cht=tx&chl=%246%5E3%24
    = 7 x 7 x 7 (指向 1)

  其中,
  https://chart.googleapis.com/chart?cht=tx&chl=%246%5E3%24 = https://chart.googleapis.com/chart?cht=tx&chl=%246%5E2%24 x 6
    = 17 x 6 (指向 7)


時鐘次方 - 共同週期

適用的數字

  與「時鐘size」互質的數字
  (不是質數的數字,仍然有可能與時鐘size 互質)

共同週期

  與「時鐘size」互質的數字的「總數」,就是共同週期

時鐘size =「質數 p」

  共同週期 = (p - 1)
  因為 1 到 (p - 1) 都和 p 互質
  
  (p - 1)次方指向 1
  p 次方指回原本的數字
  1 + 某倍(p-1)次方 也會指回原本的數字

時鐘size = 「質數 p」 X 「質數 q」

  扣掉「p的倍數」、「q的倍數」,剩下的數字就是和「時鐘size」互質
  1*p 2*p 3*p … q*p  →  q 個
  1*q 2*q 3*q … p*q  →  p 個

  共同週期 = p*q - p - q + 1
      = (p - 1) * (q - 1)
  
  (p - 1) * (q - 1)次方指向 1
  1 + 某倍(p-1)(q-1)次方 會指回原本的數字

和[時鐘size p*q] 不互質的數字(除了 p*q自己之外)

  1*p 2*p 3*p … (q-1)*p   週期:q - 1
  1*q 2*q 3*q … (p-1)*q   週期:p - 1
  所以,也適用 共同週期 (p - 1) * (q - 1)

  以 2p 為例:
  時鐘   p * q 
  2p    p * 2 * (1)

  https://chart.googleapis.com/chart?cht=tx&chl=%24(2p)%5E2%24  p * 2 * (2p)
  https://chart.googleapis.com/chart?cht=tx&chl=%24(2p)%5E3%24  p * 2 * (2p*2p)
  https://chart.googleapis.com/chart?cht=tx&chl=%24(2p)%5E4%24  p * 2 * (2p*2p*2p)
  指回原本數字 2p:
    當2p*2p*2p*… 在[時鐘size q]指向 1 時
    (q是質數,2p 和 q 互質,有機會指向 1)


RSA公開金鑰加密

時鐘size n = 「質數 p」 X 「質數 q」

時鐘上的數字 m
  有的數字和 n 互質,有的數字沒有和 n 互質
  都適用於共同週期 (p - 1) * (q - 1)

加密:
  https://chart.googleapis.com/chart?cht=tx&chl=%24m%5Ee%24 使指針指到別的數字 c

解密:
  https://chart.googleapis.com/chart?cht=tx&chl=%24c%5Ed%24 使指針指回原數字 m

https://chart.googleapis.com/chart?cht=tx&chl=%24c%5Ed%24https://chart.googleapis.com/chart?cht=tx&chl=%24(m%5Ee)%5Ed%24https://chart.googleapis.com/chart?cht=tx&chl=%24m%5E%7Bed%7D%24 ≡ m
共同週期 (p - 1) * (q - 1)的意思:
  1 + 1 (p - 1)(q - 1) 次方
  1 + 2 (p - 1)(q - 1) 次方
  1 + 3 (p - 1)(q - 1) 次方
  1 + 4 (p - 1)(q - 1) 次方
  1 + 5 (p - 1)(q - 1) 次方
    在這些次方會指回原數字
    e x d = 1 + 某倍(p - 1)(q - 1)

除了 「n = p*q」時鐘之外,
現在又多一個(p - 1)(q - 1)時鐘

選擇一個數字 e,必須與 (p - 1)(q - 1)互質
當 e 在做乘法時,才有機會指向 1 in (p - 1)(q - 1)時鐘

用「擴展歐幾里得算法」計算出 d
ed + (p - 1)(q - 1)*轉幾圈 = 1


比共同週期更小一點的週期

共同週期:(p - 1) X (q - 1)
更小一點的週期:(p - 1)和(q - 1)的最小公倍數

因為 時鐘size n = p x q (質數相乘)
時鐘上的每個數字 1 到 n
  「除以p」、「除以q」都可以獲得獨一無二的「座標」
例如:
  n = 3 x 5
  每個數字分別 「除以 3」 「除以 5」
  1 → (1,1)  6 → (0,1)  11 → (2,1)
  2 → (2,2)  7 → (1,2)  12 → (0,2)
  3 → (0,3)  8 → (2,3)  13 → (1,3)
  4 → (1,4)  9 → (0,4)  14 → (2,4)
  5 → (2,0) 10 → (1,0)  15 → (0,0)

時鐘上的某一個數字,不同次方時,(x,y)座標會改變
  次方週期 (p - 1) : x座標回復原狀
  次方週期 (q - 1) : y座標會復原狀

  次方週期 (p - 1)和(q - 1)的最小公倍數:
    x座標 y座標都會復原狀 → 也就是指回原本的數字


參考資料


圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言