Используйте QuickCheck, генерируя простые числа - PullRequest
Новая
       6

Используйте QuickCheck, генерируя простые числа

13 голосов
/ 20 февраля 2011

Фон

Ради интереса я пытаюсь написать свойство для быстрой проверки, которое может проверить основную идею криптографии с RSA .

Для всех x таких, что 1 < x < N, всегда верно, что (x^e)^d = x modulo N

Другими словами, x - это «сообщение», возведение его в e th power mod N - это действие «кодирования» сообщения и перевода закодированного сообщения в d th. power mod N - это акт «расшифровки» его.

(Свойство также тривиально верно для x = 1, случай, который имеет свое собственное шифрование)

Код

Вот методы, которые я описал до сих пор: 

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

(Спасибо, Google и случайный блог, за реализацию модульного мультипликативного обратного )

Вопрос

Проблема должна быть очевидной: слишком много условий для свойства, чтобы его вообще можно было использовать. При попытке вызвать quickCheck prop_rsa в ghci мой терминал завис.

Итак, я немного покопался в руководстве QuickCheck , и там написано:

Свойства могут принимать форму

forAll <generator> $ \<pattern> -> <property>

Как мне сделать <generator> для простых чисел? Или с другими ограничениями, чтобы quickCheck не приходилось просеивать кучу неудачных условий?

Любые другие общие советы (особенно в отношении QuickCheck) приветствуются.

Ответы [ 2 ]

4 голосов
/ 22 февраля 2011

Хорошо, вот что я сделал.

Начало файла 

{-# LANGUAGE NoMonomorphismRestriction #-}

import Test.QuickCheck
import Control.Applicative

Весь код, указанный в вопросе, кроме prop_rsa. Это было (очевидно) сильно изменено: 

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

Тип для primePair - Gen (Int, Int), а для genUnder - Int -> Gen Int. Я не совсем уверен, в чем заключается магия forAll, но я уверен, что это правильно. Я сделал некоторые специальные корректировки для 1) убедиться, что он потерпит неудачу, если я испорчу условия, и 2) убедиться, что вложенный forAll изменяет значение x в разных тестовых примерах.

Так вот, как написать эти генераторы. Как только я понял, что <generator> в документации означало что-то типа Gen a, это был торт. 

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 потребовалось несколько проб и ошибок, чтобы я понял все правильно; Я знал, что некоторые комбинаторы, подобные этому, должны работать, но я все еще не настолько знаком с fmap, <$> и <*>, как хотелось бы. Я ограничил вычисление только выбором из первых 2500 простых чисел; в противном случае он, очевидно, хотел выбрать несколько действительно больших, которые потребовались бы вечно.

Случайная вещь на заметку

Благодаря лени, d = mInverse e t не вычисляется, если не выполнены условия. Что хорошо, потому что не определено, когда условие rPrime e t ложно. В английском языке целое число a имеет только мультипликативный обратный знак (mod b), когда a и b относительно простые числа.

4 голосов
/ 20 февраля 2011

Вот один из способов сделать QuickCheck-совместимый генератор простых чисел (украсть реализацию Sieve of Eratosthenes из 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)

Может использоваться в QuickCheck следующим образом: 

prop_primes_dont_divide (Prime x) (Prime y) = x == y || x `mod` y > 0

Для вашего использования вы должны заменить p и q на (Prime p) и (Prime q) в вашей собственности.

...