我的 RSA 算法对于像“cat”这样的 3 个字母的单词工作正常,但是一旦单词变长,我就会收到一条错误消息:Exception: decipher2.hs:(37,1)-(62,19): Non-函数 numToLet 中的详尽模式
我的程序按照以下步骤运行
用于加密
- 将一串字母转换为一串数字,其中每个字母都分配给一个特定的数字。
- 将一串数字组合成一个更大的数字。
- 使用适当的 p 和 q 值,计算 n 并选择一个与 n 互质的合适数字 e(因为这是一个内部过程,对 p 和 q 保密并不重要,但可以做到)
- 执行RSA算法以产生“密码数”
用于解密
- 使用 p 和 q 计算 totient φ(n)(其中 φ(n) = (p-1) * (q-1) )
- 将寻找两个数的最大公约数的欧几里德算法写入代码。
- 将反向替换部分写入代码,使其可交换地形成扩展欧几里得算法。
- 计算私钥。
- 包括某种存储私钥的选项,这样就不需要每次都执行此功能(以提高速度)。
- 应执行RSA 加密的解密算法。
- 结果应拆分为一串数字(与加密过程第 2 阶段的合并过程相反)。
- 应将数字串转换为字母串(使用与加密过程中相同的值)。
我选择不包括计算 key 部分,因为它是一个单独的程序并且必须是正确的(因为能够破译短词)。我试过使用较小的 p 和 q 值,但这也不起作用,有人知道为什么较长的单词不起作用(即使对于较小的素数)和/或我如何解决它吗?
我的加密代码是:
import Data.List
letToNum c'' = (let (Just n) = elemIndex c'' ['a'..'z'] in n) + 10
combine = foldl addDigit 0
where addDigit num i' = (10 ^ (floor $ log (fromIntegral i') / log 10 + 1))*num + i'
firstTwo xs = toInteger (combine (map letToNum xs))
p' = 2^2048 - 1942289
q' = 2^2048 - 2^1056 + 2^736 - 2^320 + 2^128 + 1
n' = p' * q'
e' = 7
newtype ModN = ModN (Integer, Integer) deriving (Eq, Show)
instance Num ModN where
ModN (x, m) + ModN (y, m') | m == m' = ModN ((x + y) `mod` m, m)
| otherwise = undefined
ModN (x, m) * ModN (y, m') | m == m' = ModN ((x * y) `mod` m, m)
| otherwise = undefined
negate (ModN (x, m)) = ModN ((- x) `mod` m, m)
abs _ = undefined
signum _ = undefined
fromInteger _ = undefined
modPow :: Integer -> Integer -> Integer -> Integer
modPow _ 0 m = 1 `mod` m
modPow a b m = c
where a' = ModN (a, m)
ModN (c, _) = a' ^ b
encipherA z' = modPow z' e' n'
encipher xs = encipherA (firstTwo xs)
我的解密代码是:
p' = 2^2048 - 1942289
q' = 2^2048 - 2^1056 + 2^736 - 2^320 + 2^128 + 1
n' = p' * q'
d'=149198411630450358098821815816660626082852035578197682912033354754850558281651065264118115990713936905841443816348466119712510491169399086751890869693052182563708139506244285477194512876340531187775438573122278032339474119913958963667476383477798088213829701243686243438754864105731229873495425397653296705562025639940130672903361904637280085880562426594784029436599468688448179303703337724326069153629191476697420768451884440453280134491448395404958914592441919126201747433884753502442027069825305163272842897505994155682996130741544296475635538035696205346055652365820232813677363525296188331517668300986037331017823989462119054758685224752255850280255541024098528388784743634162996954090230161430468033874779937253936100340449079832503240200984659315256173082971785802328581652375418902448324739292188909509903808503871246982928186837296358844444348158079557757543904495890483033995844854839625810784987612815774450940850973031117459144355531047129541648317845165848539683500066541165782574432790936862217277817101197569391139502130923768985262346549685855947859864917650782062626099395684514986479824104485607000960030713840667632064934158997031779846656288570984548383771118345091911988849410656041321592285731293207858515766711
newtype ModN = ModN (Integer, Integer) deriving (Eq, Show)
instance Num ModN where
ModN (x, m) + ModN (y, m') | m == m' = ModN ((x + y) `mod` m, m)
| otherwise = undefined
ModN (x, m) * ModN (y, m') | m == m' = ModN ((x * y) `mod` m, m)
| otherwise = undefined
negate (ModN (x, m)) = ModN ((- x) `mod` m, m)
abs _ = undefined
signum _ = undefined
fromInteger _ = undefined
modPow :: Integer -> Integer -> Integer -> Integer
modPow _ 0 m = 1 `mod` m
modPow a b m = c
where a' = ModN (a, m)
ModN (c, _) = a' ^ b
decipherA c' = modPow c' d' n'
numToLet "10" = "a"
numToLet "11" = "b"
numToLet "12" = "c"
numToLet "13" = "d"
numToLet "14" = "e"
numToLet "15" = "f"
numToLet "16" = "g"
numToLet "17" = "h"
numToLet "18" = "i"
numToLet "19" = "j"
numToLet "20" = "k"
numToLet "21" = "l"
numToLet "22" = "m"
numToLet "23" = "n"
numToLet "24" = "o"
numToLet "25" = "p"
numToLet "26" = "q"
numToLet "27" = "r"
numToLet "28" = "s"
numToLet "29" = "t"
numToLet "30" = "u"
numToLet "31" = "v"
numToLet "32" = "w"
numToLet "33" = "x"
numToLet "34" = "y"
numToLet "35" = "z"
output xs = putStrLn $ concat (map numToLet xs)
partition :: Int -> [a] -> [[a]]
partition _ [] = []
partition n xs = (take n xs) : (partition n (drop n xs))
decipher j' = map numToLet (partition 2 (show (decipherA j')))
感谢您的帮助,我真的很感激。
最佳答案
由于 RSA 算法输出的数字小于模 n
,显然您不能加密超过 n
条不同的消息(消息 0
到 n - 1
)。
*RSA> decipherA (encipherA (n' - 1)) == n' - 1
True
*RSA> decipherA (encipherA n') == n'
False
对于超过特定长度的字符串,您将超过该阈值。
典型的解决方案是仅使用 RSA 来加密随机生成的 session key 。然后使用此 session key 对消息进行对称加密(例如,使用 AES )。对方可以使用RSA重构 session key ,解密消息。
编辑: 我刚刚看到,除了 RSA 算法本身的这种不可避免的限制之外,您在某个地方在字符串编码中引入了另一个错误。您的编码器和解码器不适合放在一起:
*RSA> let encode = firstTwo
*RSA> let decode x = map numToLet (partition 2 (show x))
*RSA> decode (encode "catcatcatcat")
["x","g","f","c","*** Exception: RSA.hs:(41,1)-(66,19): Non-exhaustive patterns in function numToLet
问题是整数溢出:combine
的类型是 [Int] -> Int
,但是 Int
只能容纳 的值>2^31 - 1
,对应你编码中的4个字符。您可以使用 Integer
解决这个问题:
letToNum :: Char -> Integer
letToNum c'' = (let (Just n) = fmap toInteger (elemIndex c'' ['a'..'z']) in n) + 10
combine :: [Integer] -> Integer
combine = foldl addDigit 0
where addDigit num i' = 100*num + i'
firstTwo xs = combine (map letToNum xs)
如您所见,它有助于添加类型签名。我还删除了 log
表达式,我不知道它是什么意思,但我猜它要么是不必要的,要么是错误的......
关于algorithm - 我的 RSA 算法只适用于非常短的单词,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22309821/