Поиск простых чисел N̷e̷m̷o̷

Ключевая надежность RSA достигается за счет умножения двух простых чисел (p и q), чтобы получить N. Если мы получим p и q, то сможем решить:

Phi = (p-1)(q-1)

А так как у нас есть ключ шифрования (e), который обычно равен 65 537, мы находим d в:

d x e mod (PHI) = 1

В основном у нас есть мод, обратный e mod PHI. Например, если у нас есть значение e 65 537 и PHI 10 347 768 518 374 182 260, тогда значение ключа дешифрования (d) будет 12 406 113 933 120 080 Тест.

И поэтому становится легко взломать RSA, если мы сможем взломать N. Но когда мы определяем, что цифровой сертификат имеет 2048 бит, насколько велики значения p и q. Хорошо, если у нас есть значение n бит и умножаем его на значение m бит, мы получаем результат, который имеет n + m бит. Итак, если наши ключи RSA имеют длину 2048 бит, то наши простые числа будут вдвое меньше (1024 бита).

Итак, сколько цифр будет иметь 1204 бита? Ну, мы использовали Python, чтобы определить, что он имеет 309 цифр:

>>> y=2**1024
>>> print y,len(str(y))
179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137216 309

и когда мы умножаем, мы получаем 617-значное число.

>>> y=2**2048
>>> print y,len(str(y))
32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525166389437335543602135433229604645318478604952148193555853611059596230656 617

В колонке Мартина Гарднера, впервые предложившего метод RSA, задача состояла в том, чтобы взломать значение N, состоящее всего из 129 цифр, и это было бы довольно легко взломать сегодня (но в то время Рон Ривест считал, что для разложения на множители потребуется 40 квадриллионов лет). ).

Итак, если я хочу сгенерировать два простых числа, какой процесс я выберу?

Что ж, мы снова можем обратиться к Python и использовать метод Римана для оценки количества простых чисел длиной 1024 бита:

import sys
import math
start=2**1023
end=2**1024
from mpmath import *
n=int(riemannr(end))-int(riemannr(start))
print "Est prime numbers :\t",n
print "Estimation to find is 1 in",(2**1024)/n

Если мы запустим, мы обнаружим, что у нас есть огромное количество 1024-битных чисел, но шансы найти одно из них равны 1 к 1418.

Est prime numbers : 12669164489297035838042749092693935645472324718849614339
24766525026995310075958371294812932404687423824670251209
13518137109729182502216808596722503552506608383945568062
99217183402234779768002807879623065822080202513999439628
97095578902630452877769836056051748736023462240653644712
9531599628766639300804608
Estimation to find is 1 in 1418

Итак, мы можем сгенерировать 1024-битное число с помощью функции getranbits():

>>> import random
>>> random.getrandbits(1024)
156548939571986617936593398696487626269281069361549954872290664955514361566028430228393690460599919225561780089634158011587614280666963754668325779987475479846196199822356717682549864936396590068357782045162223432591023551799214794233281216026354993428635528007054022288847392617709977816846850992096404056283L
>>> random.getrandbits(1024)
55136965950425835689158416465806396636650650968403266989581732336809191724275683828621859295706434070151101183614258416403031972397870140768974504109826757341964250565697908008752691622930769593895629599534356491697781910973306456605765264018712506188755530370692209478031117756834222205525907403426552222412L

А затем проверьте, является ли это простым числом. Если нет, мы уменьшаем его и снова тестируем. По нашим расчетам, чтобы найти его, потребуется всего 1418 попыток.

Итак, теперь у нас есть целочисленный код для проверки на простое число. В этом случае я буду использовать тест Миллера-Рабина:

import sys
import math
import random
_mrpt_num_trials = 5 # number of bases to test
 
testval=97
def is_probable_prime(n):
 assert n >= 2
 # special case 2
 if n == 2:
 return True
 # ensure n is odd
 if n % 2 == 0:
 return False
 # write n-1 as 2**s * d
 # repeatedly try to divide n-1 by 2
 s = 0
 d = n-1
 while True:
 quotient, remainder = divmod(d, 2)
 if remainder == 1:
 break
 s += 1
 d = quotient
 assert(2**s * d == n-1)
 
 # test the base a to see whether it is a witness for the compositeness of n
 def try_composite(a):
 if pow(a, d, n) == 1:
 return False
 for i in range(s):
 if pow(a, 2**i * d, n) == n-1:
 return False
 return True # n is definitely composite
 
 for i in range(_mrpt_num_trials):
 a = random.randrange(2, n)
 if try_composite(a):
 return False
 
 return True
val = random.getrandbits(1024)
for x in range(4000):
 test = val-x
 if is_probable_prime(test):
 print “Found:”,test

Пример запуска дает:

Found: 10984678770764623323878741084947969949832629371144544237407544
03337401646290765857178780855834946507972652578128966513242618
23972954301989454562457411611669237492575018934204254111240208
39166423426856896124038258075724310959568802347236784318963962
9754396454368329186198846985241378274571141217417474768124739

Итак, мы нашли ̶N̶e̶m̶o̶ простых чисел.