13

背景

为了好玩，我正在尝试编写一个用于快速检查的属性，该属性可以使用 RSA 测试密码学背后的基本思想。

  • 选择两个不同的素数，p并且q。
  • 让N = p*q
  • e是某个相对质数的数(p-1)(q-1)（实际上，对于快速编码，e 通常为 3）
  • d是模的模逆e(p-1)(q-1)

对于所有x这些，1 < x < N总是正确的(x^e)^d = x modulo N

换句话说，x是“消息”，将其提升到eth power modN是对消息“编码”的行为，将编码的消息提升到dth power modN是“解码”它的行为。

（该属性对于 也是微不足道的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 和 random 博客，用于模乘逆的实现）

问题

问题应该很明显：该属性的条件太多，无法使其完全可用。尝试quickCheck prop_rsa在 ghci 中调用使我的终端挂起。

所以我浏览了一下QuickCheck 手册，上面写着：

属性可以采取的形式

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

<generator>我如何为素数做一个？或者使用其他约束，这样quickCheck就不必筛选一堆失败的条件？

欢迎任何其他一般性建议（尤其是关于 QuickCheck）。

4

2 回答 2

4

好的，这就是我所做的。

文件顶部

{-# 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） 。ab

于 2011-02-22T19:34:38.600 回答
4

这是制作兼容 QuickCheck 的素数生成器的一种方法（从http://en.literateprograms.org/Sieve_of_Eratosthenes_(Haskell ) 窃取 Eratosthenes 的筛子实现）：

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

为了您的使用，您可以将pandq替换为(Prime p)and(Prime q)在您的财产中。

于 2011-02-20T06:30:02.820 回答