Verwenden Sie QuickCheck, indem Sie Primzahlen generieren
-
15-11-2019 - |
Frage
Hintergrund
Zum Spaß versuche ich, eine Eigenschaft für die Schnellprüfung zu schreiben, die die Grundidee dahinter testen kann kryptographie mit RSA.
- Wählen Sie zwei verschiedene Primzahlen,
p
undq
. - Lassen
N = p*q
e
ist eine Zahl relativ prime zu(p-1)(q-1)
(in der Praxis ist e normalerweise 3 für eine schnelle Codierung.)d
ist der modulares inverses vone
modulo(p-1)(q-1)
Für alle x
so dass 1 < x < N
, es ist immer wahr, dass (x^e)^d = x modulo N
Mit anderen Worten:, x
ist die "Botschaft", die sie an die e
th Macht mod N
ist der Vorgang des "Codierens" der Nachricht und des Anhebens der codierten Nachricht an die d
th Macht mod N
ist der Akt des "Entschlüsselns".
(Die Eigenschaft ist auch trivial wahr für x = 1
, ein Fall, der seine eigene Verschlüsselung ist)
Codes
Hier sind die Methoden, die ich bisher codiert habe:
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
(Danke, Google und zufälliger Blog, für die implementierung der modularen multiplikativen inversen)
Frage
Das Problem sollte offensichtlich sein:es gibt viel zu viele Bedingungen auf dem Grundstück, um es überhaupt nutzbar zu machen.Versuchen aufzurufen quickCheck prop_rsa
in ghci hat mein Terminal hängen gelassen.
Also habe ich mich um die gekümmert QuickCheck Anleitung ein bisschen, und es sagt:
Eigenschaften können die Form annehmen
forAll <generator> $ \<pattern> -> <property>
Wie mache ich eine <generator>
für Primzahlen?Oder mit den anderen Einschränkungen, so dass quickCheck
muss man nicht eine Reihe von gescheiterten Bedingungen durchforsten?
Alle anderen allgemeinen Ratschläge (insbesondere zum QuickCheck) sind willkommen.
Lösung 2
OK, also hier ist was ich getan habe.
Anfang der Datei
{-# LANGUAGE NoMonomorphismRestriction #-}
import Test.QuickCheck
import Control.Applicative
Der gesamte Code wie in der Frage angegeben, mit Ausnahme von prop_rsa.Das wurde (offensichtlich) stark modifiziert:
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
Der Typ für primePair
is Gen (Int, Int)
, und der Typ für genUnder
is Int -> Gen Int
.Ich bin mir nicht ganz sicher, was die Magie dahinter steckt forAll
aber ich bin mir ziemlich sicher, dass das richtig ist.Ich habe einige Ad-hoc-Anpassungen vorgenommen, um 1) sicherzustellen, dass es fehlschlägt, wenn ich die Bedingungen durcheinander bringe, und 2) sicherzustellen, dass die verschachtelten forAll
variiert der Wert von x
über Testfälle hinweg.
Also hier ist, wie man diese Generatoren schreibt.Einmal wurde mir klar, dass <generator>
in der Dokumentation bedeutete nur etwas vom Typ Gen a
, es war Kuchen.
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
ich brauchte ein paar Versuche und Irrtümer, um es richtig zu machen;Ich wusste, dass einige Kombinatoren so sind sollen arbeit, aber ich bin immer noch nicht so vertraut mit fmap
, <$>
und <*>
so wie ich gerne wäre.Ich habe die Berechnung darauf beschränkt, nur aus den ersten 2500 Primzahlen auszuwählen;ansonsten wollte es anscheinend einige wirklich große auswählen, deren Generierung ewig gedauert hat.
Zufällige Sache zu beachten
Dank Faulheit, d = mInverse e t
wird nicht berechnet, es sei denn, die Bedingungen sind erfüllt.Was gut ist, weil es undefiniert ist, wenn die Bedingung rPrime e t
ist falsch.Im Englischen eine ganze Zahl a
hat nur eine multiplikative Inverse (mod b), wenn a
und b
sind relativ prime.
Andere Tipps
Hier ist eine Möglichkeit, einen QuickCheck-kompatiblen Primzahlengenerator zu erstellen (ein Sieb der Eratosthenes-Implementierung zu stehlen 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)
Es kann im QuickCheck wie folgt verwendet werden:
prop_primes_dont_divide (Prime x) (Prime y) = x == y || x `mod` y > 0
Für Ihren Gebrauch würden Sie ersetzen p
und q
mit (Prime p)
und (Prime q)
in Ihrem Eigentum.