Usa QuickCheck generando numeri primi
-
15-11-2019 - |
Domanda
Sfondo
Per divertimento, sto cercando di scrivere una proprietà per il controllo rapido che può testare l'idea di base dietro crittografia con RSA.
- Scegli due numeri primi distinti,
p
eq
. - Lasciare
N = p*q
e
è un numero relativamente primo per(p-1)(q-1)
(in pratica, e è di solito 3 per la codifica veloce)d
è il modular inverse die
modulo(p-1)(q-1)
Per tutti x
tale che 1 < x < N
, è sempre vero che (x^e)^d = x modulo N
In altre parole, x
è il "messaggio", elevandolo al e
th potenza mod N
è l'atto di "codificare" il messaggio e di elevare il messaggio codificato al d
th potenza mod N
è l'atto di "decodificarlo".
(La proprietà è anche banalmente vera per x = 1
, un caso che è la sua propria cifratura)
Codice
Ecco i metodi che ho codificato finora:
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
(Grazie, google e random blog, per il implementazione dell'inverso moltiplicativo modulare)
Domanda
Il problema dovrebbe essere ovvio:ci sono troppe condizioni sulla proprietà per renderla utilizzabile.Cercando di invocare quickCheck prop_rsa
in ghci fatto il mio terminale appendere.
Così ho frugato intorno al Manuale QuickCheck un po', e dice:
Le proprietà possono assumere la forma
forAll <generator> $ \<pattern> -> <property>
Come faccio a fare un <generator>
per i numeri primi?O con gli altri vincoli, in modo che quickCheck
non deve passare al setaccio un sacco di condizioni fallite?
Qualsiasi altro consiglio generale (in particolare per quanto riguarda QuickCheck) è il benvenuto.
Soluzione 2
OK, ecco cosa ho fatto.
Inizio del file
{-# LANGUAGE NoMonomorphismRestriction #-}
import Test.QuickCheck
import Control.Applicative
Tutto il codice come indicato nella domanda, ad eccezione di prop_rsa.Questo è stato (ovviamente) pesantemente modificato:
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
Il tipo per primePair
essere Gen (Int, Int)
, e il tipo per genUnder
essere Int -> Gen Int
.Non so esattamente cosa ci sia dietro la magia forAll
ma sono abbastanza sicuro che sia corretto.Ho fatto alcune regolazioni ad-hoc per 1) assicurarsi che non riesca se rovino le condizioni e 2) assicurarsi che il nidificato forAll
varia il valore di x
attraverso casi di test.
Quindi ecco come scrivere quei generatori.Una volta ho capito che <generator>
nella documentazione significava solo qualcosa di tipo Gen a
, era torta.
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
ci sono voluti alcuni tentativi ed errori per me per avere ragione;Sapevo che alcuni combinatori del genere dovere lavoro, ma non sono ancora così familiare con fmap
, <$>
e <*>
come vorrei essere.Ho limitato il calcolo a selezionare solo tra i primi 2500 numeri primi;in caso contrario, a quanto pare voleva scegliere alcuni davvero grandi che hanno preso per sempre per generare.
Cosa casuale da notare
Grazie alla pigrizia, d = mInverse e t
non viene calcolato a meno che non siano soddisfatte le condizioni.Che è buono, perché non è definito quando la condizione rPrime e t
è falso.In inglese, un intero a
ha solo un inverso moltiplicativo (mod b) quando a
e b
sono relativamente primi.
Altri suggerimenti
Ecco un modo per creare un generatore di numeri primi compatibile con QuickCheck (rubando un setaccio di implementazione di Eratostene da http://en.literateprograms.org/Sieve_of_Eratosthenes_ (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)
Può essere utilizzato in QuickCheck in questo modo:
prop_primes_dont_divide (Prime x) (Prime y) = x == y || x `mod` y > 0
Per il tuo uso, sostituiresti p
e q
con (Prime p)
e (Prime q)
nella tua proprietà.