Use QuickCheck gerando números primos
-
15-11-2019 - |
Pergunta
Fundo
Por diversão, estou tentando escrever uma propriedade para verificação rápida que possa testar a ideia básica por trás criptografia com RSA.
- Escolha dois primos distintos,
p
eq
. - Deixar
N = p*q
e
é algum número relativamente nobre para(p-1)(q-1)
(na prática, e geralmente é 3 para codificação rápida)d
é o modular inverso dee
módulo(p-1)(q-1)
Para todos x
de tal modo que 1 < x < N
, é sempre verdade que (x^e)^d = x modulo N
Em outras palavras, x
é a "mensagem", elevando-a ao e
o mod de energia N
é o ato de "codificar" a mensagem e elevar a mensagem codificada ao d
o mod de energia N
é o ato de "decodificá-lo".
(A propriedade também é trivialmente verdadeira para x = 1
, um caso que é sua própria criptografia)
Código
Aqui estão os métodos que codifiquei até agora:
import Test.QuickCheck
-- modular exponentiation
modExp :: Integral a => a -> a -> a -> a
modExp y z n = modExp' (y `mod` n) z `mod` n
where modExp' y z | z == 0 = 1
| even z = modExp (y*y) (z `div` 2) n
| odd z = (modExp (y*y) (z `div` 2) n) * y
-- relatively prime
rPrime :: Integral a => a -> a -> Bool
rPrime a b = gcd a b == 1
-- multiplicative inverse (modular)
mInverse :: Integral a => a -> a -> a
mInverse 1 _ = 1
mInverse x y = (n * y + 1) `div` x
where n = x - mInverse (y `mod` x) x
-- just a quick way to test for primality
n `divides` x = x `mod` n == 0
primes = 2:filter isPrime [3..]
isPrime x = null . filter (`divides` x) $ takeWhile (\y -> y*y <= x) primes
-- the property
prop_rsa (p,q,x) = isPrime p &&
isPrime q &&
p /= q &&
x > 1 &&
x < n &&
rPrime e t ==>
x == (x `powModN` e) `powModN` d
where e = 3
n = p*q
t = (p-1)*(q-1)
d = mInverse e t
a `powModN` b = modExp a b n
(Obrigado, google e blog aleatório, pela implementação de inverso multiplicativo modular)
Pergunta
O problema deveria ser óbvio:há muitas condições na propriedade para torná-la utilizável.Tentando invocar quickCheck prop_rsa
no ghci fez meu terminal travar.
Então eu vasculhei o Manual do QuickCheck um pouco e diz:
As propriedades podem assumir a forma
forAll <generator> $ \<pattern> -> <property>
Como faço um <generator>
para números primos?Ou com as outras restrições, de modo que quickCheck
não precisa examinar um monte de condições que falharam?
Qualquer outro conselho geral (especialmente em relação ao QuickCheck) é bem-vindo.
Solução 2
OK, então aqui está o que eu fiz.
Início do arquivo
{-# LANGUAGE NoMonomorphismRestriction #-}
import Test.QuickCheck
import Control.Applicative
Todo o código fornecido na pergunta, exceto prop_rsa.Isso foi (obviamente) fortemente modificado:
prop_rsa = forAll primePair $ \(p,q) ->
let n = p*q
in forAll (genUnder n) $ \x ->
let e = 3
t = (p-1)*(q-1)
d = mInverse e t
a `powModN` b = modExp a b n
in p /= q &&
rPrime e t ==>
x == (x `powModN` e) `powModN` d
O tipo para primePair
é Gen (Int, Int)
, e o tipo para genUnder
é Int -> Gen Int
.Não sei exatamente qual é a magia por trás forAll
mas tenho certeza que isso está correto.Fiz alguns ajustes ad-hoc para 1) garantir que ele falhe se eu bagunçar as condições e 2) garantir que o aninhamento forAll
está variando o valor de x
em todos os casos de teste.
Então aqui está como escrever esses geradores.Uma vez que eu percebi isso <generator>
na documentação significava apenas algo do tipo Gen a
, era bolo.
genNonzero = (\x -> if x == 0 then 1 else x) `fmap` arbitrary
genUnder :: Int -> Gen Int
genUnder n = ((`mod` n) . abs) `fmap` genNonzero
genSmallPrime = ((\x -> (primes !! (x `mod` 2500))) . abs) `fmap` arbitrary
primePair :: Gen (Int, Int)
primePair = (,) <$> genSmallPrime <*> genSmallPrime
primePair
foram necessárias algumas tentativas e erros para acertar;Eu sabia que alguns combinadores assim deve trabalho, mas ainda não estou tão familiarizado com fmap
, <$>
e <*>
como eu gostaria de ser.Restringi o cálculo para selecionar apenas entre os primeiros 2.500 primos;caso contrário, aparentemente queria escolher alguns realmente grandes que demoravam uma eternidade para serem gerados.
Coisa aleatória a ser observada
Graças à preguiça, d = mInverse e t
não é calculado a menos que as condições sejam atendidas.O que é bom, porque é indefinido quando a condição rPrime e t
é falso.Em inglês, um número inteiro a
só tem um inverso multiplicativo (mod b) quando a
e b
são relativamente primos.
Outras dicas
Aqui está uma maneira de criar um gerador de números primos compatível com QuickCheck (roubando uma implementação do Sieve of Eratosthenes de http://en.literateprograms.org/Sieve_of_Eratostenes_(Haskell)):
import Test.QuickCheck
newtype Prime = Prime Int deriving Show
primes = sieve [2..]
where
sieve (p:xs) = Prime p : sieve [x | x <- xs, x `mod` p > 0]
instance Arbitrary Prime where
arbitrary = do i <- arbitrary
return $ primes!!(abs i)
Ele pode ser usado no QuickCheck assim:
prop_primes_dont_divide (Prime x) (Prime y) = x == y || x `mod` y > 0
Para seu uso, você substituiria p
e q
com (Prime p)
e (Prime q)
em sua propriedade.