استخدم QuickCheck عن طريق توليد الأعداد الأولية

Question

خلفية

من أجل المتعة، أحاول كتابة خاصية للتحقق السريع والتي يمكنها اختبار الفكرة الأساسية وراءها التشفير باستخدام RSA.

• اختر عددين أوليين مختلفين، p و q.
• يترك N = p*q
• e هو بعض العدد رئيس نسبيا ل (p-1)(q-1) (عمليا، e عادة ما يكون 3 للتشفير السريع)
• d هل معكوس وحدات ل e modulo (p-1)(q-1)

للجميع x مثل ذلك 1 < x < N, ، صحيح دائما أن (x^e)^d = x modulo N

بعبارة أخرى، x هي "الرسالة"، ورفعها إلى eوضع الطاقة N هي عملية "تشفير" الرسالة ورفع الرسالة المشفرة إلى ملف dوضع الطاقة 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_rsa في ghci جعل محطتي معطلة.

لذلك قمت بدس حول دليل الفحص السريع قليلاً، فيقول:

قد تأخذ الخصائص النموذج

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

كيف أقوم بعمل <generator> للأعداد الأولية؟أو مع القيود الأخرى، بحيث quickCheck ليس من الضروري التدقيق في مجموعة من الشروط الفاشلة؟

نرحب بأي نصيحة عامة أخرى (خاصة فيما يتعلق بـ QuickCheck).

Answer 1

حسنًا، هذا ما فعلته.

أعلى الملف

{-# 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 استغرق الأمر بعض التجربة والخطأ حتى أصل إلى الصواب؛كنت أعرف أن بعض combinators من هذا القبيل يجب العمل، ولكن ما زلت لست على دراية fmap, <$> و <*> كما أود أن أكون.لقد قمت بقصر الحساب على الاختيار فقط من بين أول 2500 عدد أولي؛وإلا فمن الواضح أنها أرادت اختيار بعض العناصر الكبيرة التي استغرق إنشاؤها وقتًا طويلاً.

شيء عشوائي أن نلاحظ

بفضل الكسل، d = mInverse e t ولا يتم احتسابه إلا إذا استوفيت الشروط.وهو أمر جيد، لأنه غير محدد عند الشرط rPrime e t هو زائف.في اللغة الإنجليزية، عدد صحيح a يحتوي فقط على معكوس مضاعف (mod b) متى a و b هي أولية نسبيا.

Answer 2

إليك إحدى الطرق لإنشاء مولد أرقام أولية متوافق مع QuickCheck (سرقة تطبيق Sieve of Eratosthenes من http://en.literateprograms.org/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) في الممتلكات الخاصة بك.