Въведение

Гледа ли урока по Съвременна криптография? При последната проверка това беше най-популярният въпрос, задаван от потребителите:

В урока видяхме как разлагането на числото на прости множители играе основна роля в изграждането на математически ключалки или катинари. Математическият катинар (или еднопосочна функция) изисква процедура, която е лесна за изпълнение и трудна за обръщане.

Например ако произволно избереш две големи прости числа като: P1 = 709 и P2 = 733

и ги умножи така:  N = P1 * P2

N = 709 * 733 = 519697 (това ще се изчисли лесно )

Получават се две неща: голямо число (519697) и простите множители на това голямо число (709 * 733)

Сега си представи, че аз скривам тези прости множители и оставям само следното:

519697 =? *? (това е трудно да се изчисли)

Ако те помоля да намериш простите множители на това число,  откъде ще започнеш? Не се притеснявай, всеки се затруднява с тази задача! За да намериш решение, трябва да направиш куп тестове, опити и грешки. Умножението е бърз (лесен) начин за пресмятане, докато разлагането на прости множители е бавно (сложно). Този прост факт поставя основата на RSA схемата на шифроване.

👁️ Watch this animated graph to see the difference.

Но преди да продължим, трябва да се фокусираме върху първата стъпка и да си зададем един важен въпрос. Когато казваме, че "случайно избираме две големи прости числа", как да направим това бързо? Това лесна задача ли е?

Ако помислиш върху това, накрая ще се съгласиш, че тази стъпка изисква поне способностт да проверим дали едно случайно генерирано число (като 99194853094755497) е просто или съставно. Има ли бутон на калкулатора, който да може да даде този отговор?

Не виждам такъв бутон…. Защо ли?

За да разберем, нека започнем с едно предизвикателство...