Paillier

ペイエ暗号 (加法準同型性を満たす)

Haskell コード

import Crypto.Number.ModArithmetic
l :: Integer -> Integer
l x = (x - 1) `div` n
solve :: Integer -> Integer
solve c = (l (expSafe c lambda (n^2)) * mu) `mod` n
where
lambda = lcm (p-1) (q-1)
mu = inverseCoprimes (l (expSafe g lambda (n^2))) n

具体例

import Crypto.Number.ModArithmetic
import Crypto.Number.Serialize
import Data.Text
import Data.Text.Encoding
p, q, n, g, c :: Integer
p = 310013024566643256138761337388255591613
q = 319848228152346890121384041219876391791
n = 99157116611790833573985267443453374677300242114595736901854871276546481648883
g = 99157116611790833573985267443453374677300242114595736901854871276546481648884
c = 2433283484328067719826123652791700922735828879195114568755579061061723786565164234075183183699826399799223318790711772573290060335232568738641793425546869
l :: Integer -> Integer
l x = (x - 1) `div` n
solve :: Integer -> Integer
solve c = (l (expSafe c lambda (n^2)) * mu) `mod` n
where
lambda = lcm (p-1) (q-1)
mu = inverseCoprimes (l (expSafe g lambda (n^2))) n
toDisplay :: Integer -> Text
toDisplay = decodeUtf8 . i2osp

実行結果

*Main> solve c
8483734412270322850839331621532480687141757
*Main> toDisplay $ solve c
"actf{crypto_lives}"

参考リソース