Добре дошли в Светът на Байта. В този пост ще видим каква тайна е скрита зад врата с номер 57.
Врата номер 57 се отключва с 3 и 19 и нейното отключване в играта „Бялата шапка и древният ключ“ носи 4 точки.
Тайната зад тази врата е свързана с полупростите числа. Полупрости наричаме числата, които са произведение от две прости числа. Тези числа нямат собствени делители, които не са прости числа. Полупростите имат няколко приложения в криптографията и числените методи, но най-забележителното им използване е в криптографията с публичен ключ.
Обикновеното шифриране има един основен проблем – подателят и получателят трябва да имат един и същ ключ, за да шифрират и дешифрират съобщението.
Ако имаш една дума, е много лесно да познаеш буквите, от които е съставена. Ако обаче имаш разбъркани буквите, е доста по-трудно да намериш думата, за която са те.

Задача 1: Коя е думата съставена от буквите К,Б,О,Ъ,Р,И,Я,Т?

В такива случаи казваме, че сложността е асиметрична. Едното действие е лесно, обратното е много по-трудно.

Асиметричен по сложност е и случаят с разлагането на множители. Ако имаш няколко прости числа, е лесно да намериш тяхното произведение. Ако обаче имаш произведението, то е много по-трудно да намериш простите множители, от които то е изградено.

Задача 2: Как се разлага на прости множители числото 1168283?

През 1978 г. Рон Ривест, Ади Шамир и Леонард Адълман описват алгоритъма, известен като RSA. Наречен е така на първите букви от имената на създателите си. Този алгоритъм позволява да се шифрира с един ключ (частен ключ), а да се дешифрира с друг ключ (публичен ключ). Публичният ключ представлява много голямо полупросто число, а частния ключ е единият от неговите делители.
Това, което прави този алгоритъм толкова ценен, е, че само човек, който знае частния ключ може да криптира съобщенията. Всеки притежател на публичен ключ може да прочете съобщението, но само притежателя на частния ключ може да го напише. Това гарантира електронната идентификация на подателя на дадено съобщение.
Подробно описание на алгоритъма можете да намерите в книгата „Наръчник на бунтаря за проваляне на часа по математика“

Сега ще дадем само няколко насоки.

1. Започваме с двойка прости числа. В реалния свят, те трябва да са поне 512 позиции. За да разберем как работи ще вземем по-малки числа. Например p=11 и q=13
2. Изчисляваме произведението n=p*q. В нашия случай n=11*13=143
3. Изчисляваме произведението w(n)=(p-1)*(q-1). В нашия случай w(143)=(11-1)*(13-1)=10*12=120 или w(n)=120
4. Сега идва момента на избор на ключ. Избираме случайно просто число e, което е взаимно просто с w(n) и е по-малко от него. В нашия случай можем да изберем e=7. Да отбележим, че не може да изберем 2,3 или 5 защото и трите са делители на 120.
5. Изчисляваме d такова, че произведението d*e дава остатък 1 при делене на n. В нашия случай търсим d*7=k*120+1. Или в нашия случай d=103; k=6. Наистина 103*7=721; 6*120+1=721.
6. Готови сме – двойката (e;n) е часния ключ и служи за криприране, а двойката (d;n) е публичния ключ и служи за декриприране. Ние криптираме с двойката (7;143), получателят декриптира с двойката (103;143)

Нека m е нашето оригинално съобщение. Тогава m^emod(n) е нашето криптирано съобщение. Да го означим с c. Получателя декриптира с c^dmod(n). Разбира се всички тези сметки ги правят компютрите.

Компютърна реализация за първоначално запознаване с RSA можеш да използваш от хранилището за компютърен код Rossete.org
https://rosettacode.org/wiki/RSA_code

Това беше тайната скрита зад врата 57.

Кратко видео за тайната скрита зад вратa 57 можете да видите на нашия видеоканал тук.

“Светът на Байта – естествените числа” можете да поръчате тук.

Вижте и останалите загадки скрити зад вратите от Светът на Байта и успех в играта!

Сгъни наука

Copyright © 2018 Мариела Станчева|Website Design by Blue Gem Studios