Криптография

Съдържание

Ето я най-важната част. Всички знаем защо си тук. :)

Задачи за домашно и решения
добър зъболекар пловдив


1. Класическа криптография
2. Криптанализ на класически криптосистеми
3. Теория на Шенон
4. Поточни шифри
5. Блокови шифри - Des, Rijndael
6. Асиметрични криптосистеми
7. RSA
8. Криптосистеми, основани на дискретни логаритми. Задача за намиране на дискретен логаритъм

лесна задача: имаме а, имаме р, трябва да намерим ар. Това може да стане със сложност log p.
трудна задача: имаме а, имаме колко е ар = b, трябва да намерим р. Разбира се, p = logab. Само дето намирането на logab е трудна операция, а не бихме искали да проверяваме дали р = 1, 2, … та дано уцелим.

9. Задача за генериране на големи прости числа
задача: Дадено е число p. Просто ли е? Един евристичен алгоритъм за решаването на тази задача използва следното свойство на простите числа:
ако p e просто и НОД(а,p) =1, то $a^{p-1} \equiv 1 (mod \enspace p)$. Това е Малката Теорема на Ферма. Затова проверяваме за много стойности на а дали $a^{p-1} \equiv 1 (mod \enspace p)$. Ако винаги е така, решаваме, че p e просто. За съжаление обаче съществуват числата на Кармайкъл. Те са съставни, но все пак за тях $a^{p-1} \equiv 1 (mod \enspace p)$, ако НОД(а,p) =1. Тези числа са сравнително малко, така че методът работи добре. Но все пак можем да избегнем проблемите, като използваме квадратични остатъци.

10. Задача за намиране на дискретен логаритъм
11. Криптосистема, основаваща се на задача за раницата

проблем на асиметричното криптиране е, че е около 1000 пъти по-бавно от DES и Rijndael

12. Цифров подпис (digital signature)
13. Криптографски протоколи

генериране на случаен бит - двама човека говорят по телефона, потенциално и двамата лъжат. Как да хвърлят ези - тура.
zero knowledge proofs - имаме тайна информация, как да убедим някого, че я знаем, без да разкриваме самата информация
digital cash, untraceable cash

14. Secret sharing schemes

Комисия от n човека има сейф. За него трябва ключ. Трябва ключът да се разпредели по такъв начин между хората, че които и k от тях да се съберат, да могат да отворят сейфа, но никои k-1 да не успеят. Има и по-сложна задача - да се разпредели така ключа, че които и k-1 човека да се съберат, да нямат никаква информация за ключа (всички ключове да са равновероятни)

15. Схема за електронно гласуване

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License