通过生成素数来使用 QuickCheck

发布于 2024-10-18 09:03:40 字数 2862 浏览 1 评论 0原文

背景

为了好玩,我正在尝试编写一个用于快速检查的属性,可以测试 RSA 加密

对于所有 x ,使得 1 1 x < N(x^e)^d = x modulo N 始终为真。

换句话说,x 是“消息”,将其提升为e 次方 mod N 是对消息进行“编码”的行为,并将编码后的消息提升为 d 次方 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和随机博客,用于实现模乘法逆)

问题

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

所以我稍微浏览了一下 QuickCheck 手册,它说:

属性可以采用以下形式

forAll <生成器>; $ \<模式>; -> <属性>

如何为素数创建 ?或者使用其他约束,以便 quickCheck 不必筛选一堆失败的条件?

欢迎任何其他一般性建议(尤其是有关 QuickCheck 的建议)。

Background

For fun, I'm trying to write a property for quick-check that can test the basic idea behind cryptography with RSA.

  • Choose two distinct primes, p and q.
  • Let N = p*q
  • e is some number relatively prime to (p-1)(q-1) (in practice, e is usually 3 for fast encoding)
  • d is the modular inverse of e modulo (p-1)(q-1)

For all x such that 1 < x < N, it is always true that (x^e)^d = x modulo N

In other words, x is the "message", raising it to the eth power mod N is the act of "encoding" the message, and raising the encoded message to the dth power mod N is the act of "decoding" it.

(The property is also trivially true for x = 1, a case which is its own encryption)

Code

Here are the methods I have coded up so far:

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

(Thanks, google and random blog, for the implementation of modular multiplicative inverse)

Question

The problem should be obvious: there are way too many conditions on the property to make it at all usable. Trying to invoke quickCheck prop_rsa in ghci made my terminal hang.

So I've poked around the QuickCheck manual a bit, and it says:

Properties may take the form

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

How do I make a <generator> for prime numbers? Or with the other constraints, so that quickCheck doesn't have to sift through a bunch of failed conditions?

Any other general advice (especially regarding QuickCheck) is welcome.

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(2

随波逐流 2024-10-25 09:03:40

这是制作兼容 QuickCheck 的素数生成器的一种方法(从 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

对于您的使用,您可以替换 pq在您的属性中包含 (Prime p)(Prime q)

Here's one way to make a QuickCheck-compatible prime-number generator (stealing a Sieve of Eratosthenes implementation from 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)

It can be used in QuickCheck like so:

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

For your use, you'd replace p and q with (Prime p) and (Prime q) in your property.

┊风居住的梦幻卍 2024-10-25 09:03:40

好的,这就是我所做的。

文件顶部

{-# 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 的类型是 整数-> Gen Int。我不太确定 forAll 背后的魔力是什么,但我很确定这是正确的。我做了一些临时调整:1) 确保如果我搞乱了条件,它会失败;2) 确保嵌套的 forAll 正在改变 x 的值跨测试用例。

下面是如何编写这些生成器。当我意识到文档中的 只是意味着 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 = (,) <
gt; genSmallPrime <*> genSmallPrime

primePair 经过一些尝试和错误才得到正确的结果;我知道像这样的一些组合器应该可以工作,但我仍然不太熟悉 fmap<$>><*> 正如我所愿。我将计算限制为仅从前 2500 个素数中进行选择;否则它显然想选择一些需要很长时间才能生成的非常大的东西。

需要注意的随机事项

由于懒惰,除非满足条件,否则不会计算d = mInverse e t。这很好,因为当条件 rPrime e t 为 false 时,它​​是未定义的。在英语中,只有当 ab 互质时,整数 a 才具有乘法逆元 (mod b)。

OK so here's what I did.

Top of file

{-# LANGUAGE NoMonomorphismRestriction #-}

import Test.QuickCheck
import Control.Applicative

All code as given in the question, except for prop_rsa. That was (obviously) heavily modified:

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

The type for primePair is Gen (Int, Int), and the type for genUnder is Int -> Gen Int. I'm not exactly sure what the magic is behind forAll but I'm pretty sure this is correct. I've done some ad-hoc adjustments to 1) make sure it fails if I mess up the conditions and 2) make sure the nested forAll is varying the value of x across test cases.

So here's how to write those generators. Once I realized that <generator> in the documentation just meant something of type Gen a, it was cake.

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 = (,) <
gt; genSmallPrime <*> genSmallPrime

primePair took some trial and error for me to get right; I knew that some combinators like that should work, but I'm still not as familiar with fmap, <$> and <*> as I'd like to be. I restricted the computation to only select from among the first 2500 primes; otherwise it apparently wanted to pick some really big ones that took forever to generate.

Random thing to note

Thanks to laziness, d = mInverse e t isn't computed unless the conditions are met. Which is good, because it's undefined when the condition rPrime e t is false. In English, an integer a only has a multiplicative inverse (mod b) when a and b are relatively prime.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文