Cryptography coursera class exercise #6.

Main.hs

{-# 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)

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