1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
|
module Main
where
import Rsa
main = interact (decrypt 2036450659413645137870851576872812267542175329986469156678671505255564383842535488743101632280716717779536712424613501441720195827856504007305662157107
5282760067491066073559694937813662322539426172665930660813609694132726350877)
module Main
where
import Rsa
main = interact (prompt . keys . lines)
keys (x:y:xs) = makeKeys (read x) (read y)
prompt ks = "\nEnter two random numbers on separate lines:\n" ++
case ks of
(n,e,d) -> "The numbers n, e, and d are:\n" ++
unlines (map show [n,e,d]) ++ "\n"
module Main
where
import Rsa
main = interact (encrypt 2036450659413645137870851576872812267542175329986469156678671505255564383842535488743101632280716717779536712424613501441720195827856504007305662157107
387784473137902876992546516170169092918207676456888779623592396031349415024943784869634893342729620092877891356118467738167515879252473323905128540213)
module Rsa (encrypt, decrypt, makeKeys)
where
encrypt, decrypt :: Integer -> Integer -> String -> String
encrypt n e = unlines . map (show . power e n . code) . collect (size n)
decrypt n d = concat . map (decode . power d n . read) . lines
-------- Converting between Strings and Integers -----------
code :: String -> Integer
code = foldl accum 0
where accum x y = (128 * x) + fromIntegral (ord y)
decode :: Integer -> String
decode n = reverse (expand n)
where expand 0 = []
expand x = chr (fromIntegral (x `mod` 128)) : expand (x `div` 128)
collect :: Int -> [a] -> [[a]]
collect 0 xs = []
collect n [] = []
collect n xs = take n xs : collect n (drop n xs)
size :: Integer -> Int
size n = (length (show n) * 47) `div` 100 -- log_128 10 = 0.4745
------- Constructing keys -------------------------
makeKeys :: Integer -> Integer -> (Integer, Integer, Integer)
makeKeys p' q' = (n, invert phi d, d)
where p = nextPrime p'
q = nextPrime q'
n = p*q
phi = (p-1)*(q-1)
d = nextPrime (p+q+1)
nextPrime :: Integer -> Integer
nextPrime a = head (filter prime [odd,odd+2..])
where odd | even a = a+1
| True = a
prime p = and [power (p-1) p x == 1 | x <- [3,5,7]]
invert :: Integer -> Integer -> Integer
invert n a = if e<0 then e+n else e
where e=iter n 0 a 1
iter :: Integer -> Integer -> Integer -> Integer -> Integer
iter g v 0 w = v
iter g v h w = iter h w (g - fact * h) (v - fact * w)
where fact = g `div` h
------- Fast exponentiation, mod m -----------------
power :: Integer -> Integer -> Integer -> Integer
power 0 m x = 1
power n m x | even n = sqr (power (n `div` 2) m x) `mod` m
| True = (x * power (n-1) m x) `mod` m
sqr :: Integer -> Integer
sqr x = x * x
|
