Skip to content

Instantly share code, notes, and snippets.

@KWMalik
Forked from supki/Main.hs
Created July 30, 2012 20:04
Show Gist options
  • Save KWMalik/3209718 to your computer and use it in GitHub Desktop.
Save KWMalik/3209718 to your computer and use it in GitHub Desktop.
Cryptography coursera class exercise #6.
{-# LANGUAGE UnicodeSyntax #-}
import Data.Char (chr)
import Text.Printf (printf)
import Data.List.Split (chunk)
import Data.Number.CReal (CReal)
main ∷ IO ()
main =
do mapM_ print
[ challenge1 n1
, challenge2 n2
, challenge3 n3
]
putStrLn $ challenge4 n4
challenge1 ∷ Integer → Integer
challenge1 t =
let a = ceiling $ sqrt' $ fromIntegral t
x = round $ sqrt' $ fromIntegral $ a^2 - t
p = a - x
in p
challenge2 ∷ Integer → Integer
challenge2 t =
let as = take (2^20) [ceiling $ sqrt' $ fromIntegral t..]
xs = map (\a → round $ sqrt' $ fromIntegral $ a^2 - t) as
(p,_) = head $ dropWhile (\(x,y) → x * y /= t) $ zipWith (\a x → (a-x,a+x)) as xs
in p
challenge3 ∷ Integer → Integer
challenge3 t =
let a = subtract 1 . (2 *) . ceiling . sqrt' . fromIntegral $ 6 * t
x = round $ sqrt' $ fromIntegral (a^2 - 24 * t)
p = (a - x) `quot` 6
in p
challenge4 ∷ Integer → String
challenge4 t =
let a = ceiling $ sqrt' $ fromIntegral n1
x = round $ sqrt' $ fromIntegral $ a^2 - n1
p = a - x
q = a + x
φN = n1 - p - q + 1
m × n = (m * n) `rem` n1
e = 65537
d = inverse φN e
in map (chr . read . ("0x"++)) $ drop 1 $ dropWhile (/= "00") $ chunk 2 $ printf "0%x" $ powMod (×) t d
where
powMod ∷ (Integer → Integer → Integer) → Integer → Integer → Integer
powMod (%) _ 0 = 1
powMod (%) x' n' = f x' n' 1
where
f x n y
| n == 1 = x % y
| r == 0 = f x2 q y
| otherwise = f x2 q (x % y)
where
(q,r) = quotRem n 2
x2 = x % x
n1 ∷ Integer
n1 = 179769313486231590772930519078902473361797697894230657273430081157732675805505620686985379449212982959585501387537164015710139858647833778606925583497541085196591615128057575940752635007475935288710823649949940771895617054361149474865046711015101563940680527540071584560878577663743040086340742855278549092581
n2 ∷ Integer
n2 = 648455842808071669662824265346772278726343720706976263060439070378797308618081116462714015276061417569195587321840254520655424906719892428844841839353281972988531310511738648965962582821502504990264452100885281673303711142296421027840289307657458645233683357077834689715838646088239640236866252211790085787877
n3 ∷ Integer
n3 = 720062263747350425279564435525583738338084451473999841826653057981916355690188337790423408664187663938485175264994017897083524079135686877441155132015188279331812309091996246361896836573643119174094961348524639707885238799396839230364676670221627018353299443241192173812729276147530748597302192751375739387929
n4 ∷ Integer
n4 = 22096451867410381776306561134883418017410069787892831071731839143676135600120538004282329650473509424343946219751512256465839967942889460764542040581564748988013734864120452325229320176487916666402997509188729971690526083222067771600019329260870009579993724077458967773697817571267229951148662959627934791540
sqrt' ∷ CReal → CReal
sqrt' = sqrt
inverse ∷ Integral a ⇒ a → a → a
inverse _ 1 = 1
inverse q x = (n * q + 1) `quot` x
where
n = x - inverse x (q `rem` x)
@KWMalik
Copy link
Author

KWMalik commented Jul 30, 2012

% ./Main
13407807929942597099574024998205846127479365820592393377723561443721764030073662768891111614362326998675040546094339320838419523375986027530441562135724301
25464796146996183438008816563973942229341454268524157846328581927885777969985222835143851073249573454107384461557193173304497244814071505790566593206419759
21909849592475533092273988531583955898982176093344929030099423584127212078126150044721102570957812665127475051465088833555993294644190955293613411658629209
Factoring lets us break RSA.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment