通过生成素数来使用 QuickCheck
背景
为了好玩,我正在尝试编写一个用于快速检查的属性,可以测试 RSA 加密。
- 选择两个不同的素数:
p
和q
。 - 令
N = p*q
e
是某个数字相对prime 到(p-1)(q-1)
(实际上,为了快速编码,e 通常为 3)d
是e
模(p-1)(q-1)< 的模逆
/code>
对于所有 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
andq
. - 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 ofe
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 e
th power mod N
is the act of "encoding" the message, and raising the encoded message to the d
th 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 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(2)
这是制作兼容 QuickCheck 的素数生成器的一种方法(从 http:// en.literateprograms.org/Sieve_of_Eratosthenes_(Haskell)):
它可以在 QuickCheck 中使用,如下所示:
对于您的使用,您可以替换
p
和q
在您的属性中包含(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)):
It can be used in QuickCheck like so:
For your use, you'd replace
p
andq
with(Prime p)
and(Prime q)
in your property.好的,这就是我所做的。
文件顶部
问题中给出的所有代码(prop_rsa 除外)。这(显然)被大量修改:
primePair
的类型是Gen (Int, Int)
,genUnder
的类型是整数-> Gen Int
。我不太确定forAll
背后的魔力是什么,但我很确定这是正确的。我做了一些临时调整:1) 确保如果我搞乱了条件,它会失败;2) 确保嵌套的forAll
正在改变x
的值跨测试用例。下面是如何编写这些生成器。当我意识到文档中的
只是意味着Gen a
类型时,一切都变得简单了。primePair
经过一些尝试和错误才得到正确的结果;我知道像这样的一些组合器应该可以工作,但我仍然不太熟悉fmap
、<$>
和><*>
正如我所愿。我将计算限制为仅从前 2500 个素数中进行选择;否则它显然想选择一些需要很长时间才能生成的非常大的东西。需要注意的随机事项
由于懒惰,除非满足条件,否则不会计算
d = mInverse e t
。这很好,因为当条件 rPrime e t 为 false 时,它是未定义的。在英语中,只有当a
和b
互质时,整数a
才具有乘法逆元 (mod b)。OK so here's what I did.
Top of file
All code as given in the question, except for prop_rsa. That was (obviously) heavily modified:
The type for
primePair
isGen (Int, Int)
, and the type forgenUnder
isInt -> Gen Int
. I'm not exactly sure what the magic is behindforAll
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 nestedforAll
is varying the value ofx
across test cases.So here's how to write those generators. Once I realized that
<generator>
in the documentation just meant something of typeGen a
, it was cake.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 withfmap
,<$>
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 conditionrPrime e t
is false. In English, an integera
only has a multiplicative inverse (mod b) whena
andb
are relatively prime.