我的RSA算法适用于像"cat"这样的3个字母的单词,但是一旦单词变长,我会收到一条错误消息:异常:decipher2.hs:(37,1) - (62,19):非详尽的模式函数numToLet
我的程序按照以下步骤工作
用于加密
将一串字母转换为一串数字,其中每个字母都分配给一个特定的数字.
将数字串组合成一个更大的数字.
使用适当的p和q值,计算n并选择一个合适的数字e,它是n的共同素数(因为这是一个内部过程,保持p和q的秘密是不重要的,但可以完成)
执行RSA算法以生成"密码"
用于解密
使用p和q计算总数φ(n)(其中φ(n)=(p-1)*(q-1))
将Euclidean算法写入代码以找出两个数的最大公约数.
将后置替换部分写入代码,使其可交换地形成扩展欧几里得算法.
计算私钥.
包括存储私钥的某种选项,以便每次都不需要执行此功能(为了提高速度).
应该执行RSA加密的解密算法.
结果应该被分成一串数字(与编码过程的第2阶段中它的组合方式相反).
应将数字串转换为字母串(使用加密过程中使用的相同值).
我选择不包括计算关键部分,因为它是一个单独的程序,必须是正确的(因为短字可以被破译).我尝试使用较小的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加密随机生成的会话密钥.然后,此会话密钥用于对消息进行对称加密(例如,使用AES).另一方可以使用RSA重建会话密钥并解密消息.
编辑:我刚看到除了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
表达式,我不知道它的意图是什么,但我想这不是不必要的甚至是错误的......