13

バックグラウンド

楽しみのために、RSAを使用した暗号化の背後にある基本的な考え方をテストできるクイックチェック用のプロパティを作成しようとしています。

  • 2つの異なる素数、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は「メッセージ」であり、それをe3乗modに上げることNはメッセージを「エンコード」する行為であり、エンコードされたメッセージをd3乗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

（モジュラ逆数の実装に感謝します、グーグルとランダムブログ）

質問

問題は明らかなはずです。プロパティには条件が多すぎて、まったく使用できない状態になっています。quickCheck prop_rsaghciで呼び出そうとすると、端末がハングしました。

そこで、QuickCheckのマニュアルを少し調べてみたところ、次のようになっています。

プロパティは次の形式をとることがあります

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

<generator>素数のを作成するにはどうすればよいですか？または他の制約があるので、quickCheck失敗した状態の束をふるいにかける必要はありませんか？

その他の一般的なアドバイス（特にQuickCheckに関する）は大歓迎です。

4

2 に答える 2

4

QuickCheck互換の素数ジェネレーターを作成する1つの方法は次のとおりです（http://en.literateprograms.org/Sieve_of_Eratosthenes_(Haskell）からSieve of 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

あなたの使用のために、あなたはあなたの財産でpそしてあなたの財産で置き換えます。q(Prime p)(Prime q)

于 2011-02-20T06:30:02.820 に答える
4

OK、これが私がしたことです。

ファイルの先頭

{-# 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条件がfalseの場合は未定義なので、これは良いことです。英語では、とが互いに素である場合、整数aは乗法逆元（mod b）のみを持ちます。ab

于 2011-02-22T19:34:38.600 に答える