Re: [離散] RSA加密

[hchuang (小麥)]

(1) 若 a = bq + r , 則  k * a^p mod q = k * r^p mod q , k為常數 .

(2) 13 = 1101 ( 二進位)

    欲計算1819^13可以以下面的演算法計算 :

    令 k = 1819 , a = 1819

    從二進位表示法的第二位開始至最後一位做回圈 :

    {
      若為1 , 則 a = a^2 * k ;
      若為0 , 則 a = a^2 ;
    }

    則最後得到的a 即為 1819^13

    用例子表示的話 , 即 :


             1101                1101                   1101

1819 -> 1819^2 * 1819  -> (1819^2 * 1819)^2 -> [(1819^2 * 1819)^2]^2*1819

                                               = 1819^13


再利用(1)

=>  1819^13 mod  2537 = [(1819^2 * 1819)^2]^2*1819 mod 2537

                      = [(513 * 1819)^2]^2 * 1819 mod 2537

                      = [(2068)^2]^2 * 1819 mod 2537

                      = [1779]^2 * 1819 mod 2537

                      = 1202 * 1819 mod 2537

                      = 2081



同理  937 = 1110101001

1
1   461^2 * 461 mod 2537  = 1950 * 461 mod 2537 = 852
1   852^2 * 461 mod 2537  =  322 * 461 mod 2537 = 1296
0  1296^2 mod 2537 = 122
1   122^2 * 461 mod 2537  = 2199 * 461 mod 2537 = 1476
0  1476^2 mod 2537 = 1830
1  1830^2 * 461 mod 2537  =   60 * 461 mod 2537 = 2290
0  2290^2 mod 2537 = 121
0   121^2 mod 2537 = 1956
1  1956^2 * 461 mode 2537 =  140 * 461 mod 2537 = 1115

※ 引述《qpalwosk ( )》之銘言：
: 完整題目如下：
: http://ppt.cc/sDpl
: (94 彰師資工)
: 總之..
: 在RSA加密系統中   (公式： C = M^e mod n
:                           M = C^d mod n )
: p = 43, q = 59, n = 43*59 = 2537, e = 13
: 滿足gcd(e, (p-1)(q-1) ) = 1
: 1. 將 1819 加密
: 2. 將 461 解密
: 答案：
: 1819^13 mod 2537 = 2081
: 461^937 mod 2537 = 1115
: 請問這這麼大的數字到底怎麼算出答案？
: 還是說這題只是要把式子列出來就行了？
: thx.

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 211.74.111.149