Práce zkoumá potenciál distribuované aplikace při kryptoanalýze kryptosystémů s veřejným klíčem. V práci je uvedeno vysvětlení vztahu mezi populárními kryptosystémy s veřejným klíčem, jako je šifra RSA, Diffie-Hellmanova výměna klíčů a šifra ElGamal, a řešení problému faktorizace celých čísel nebo diskrétního logaritmu. Existují numerické metody na řešení těchto problémů, nejefektivnější z nich jsou popsány v této práci. V případě řešení problému diskrétního logaritmu, jsou zde popsány metody jako Shankův baby-step giant-step algoritmus nebo metoda index calculus. Pro účely řešení problému faktorizace celých čísel jsou zde popsány metody jako Pollardova Rho metoda, Dixonova metoda náhodných čtverců, kvadratické síto a obecné číselné síto. Téma práce bylo řešeno vytvořením distribuované aplikace. Jedná se o kompozici webové a desktopové aplikace. Webová aplikace představuje řídící uzel distribuovaného systému. Pro uživatele je využitelná při správě úloh v systému. Poskytuje také základní funkcionalitu pro distribuci úloh podřízeným uzlům. Podřízené uzly jsou reprezentovány desktopovou aplikací. Jedná se o část, kde jsou implementovány popsané numerické metody pro řešení problému faktorizace čísel či diskrétního logaritmu. Nakonec je zde analýza použitelnosti distribuované aplikace pro reálné situace. Ta je složena z měření efektivity metod a jejich potenciálu v distribuované aplikaci. Ukázalo se, že distribuovaná aplikace představuje použitelný přístup pro řešení těchto typů problémů. Nicméně se také prokázalo, že pokud neudělá kryptograf žádnou chybu během implementace popsaných systémů, je téměř nemožné být úspěšný při kryptoanalýze těchto systémů. Práce analyzuje důležité téma související bezpečností dnes používaných kryptosystémů s veřejným klíčem. Toto téma je relevantní nejen pro vědecké účely, ale má také mnoho praktických konsekvencí.
Annotation in English
The thesis studies the potential of distributed application in cryptanalysis of public-key cryptosystems. There is an explanation of the relation among a popular public-key cryptosystems, such as RSA cypher, Diffie-Hellman key exchange and ElGamal cypher, and solving of integer factorization or discrete logarithm problem. There exists numerical methods for solving of these problems, the most effective ones are described in this thesis. In the case of solving discrete logarithm problems there are described method such as Shank's baby-step giant-step algorithm and Index calculus method. For the purpose of solving integer factorization problem there are described methods such as Pollard's rho method, Dixon's random square method, Quadratic Sieve and General number field sieve. The theme of the theses was solved by creating of distributed application. It is the composition of the web application and the desktop application. The web application represents master nod in the distributed system. It is usable for managing of task in the system for the users. It also provides basic functionality for distributing of the tasks to the slave nods. The slave nod is represented by the desktop application. It is the part where there are implemented described numerical methods for solving of integer factorization or discrete logarithm problem. Finally there is an analysis of usability of the distributed application for real situations. It consists of measurements of efficiency of methods and its potentials in distributed applications. It is shown that distributed application represents usable approach for solving of this kind of problems. However it is also shown that if cryptographers does not do any mistake during implementation of described cryptosystems, it is almost impossible to be successful with cryptanalysis of such system. The thesis analyzes important issue related with security of public-key cryptosystems of nowadays. This issue is relevant not only for scientific purposes but has also many practical consequences.
Keywords
Kryptoanalýza kryptosystémů s veřejným klíčem, Distribuovaná aplikace, Problém faktorizace čísel, Problém diskrétního logaritmu, Numerické metody
Práce zkoumá potenciál distribuované aplikace při kryptoanalýze kryptosystémů s veřejným klíčem. V práci je uvedeno vysvětlení vztahu mezi populárními kryptosystémy s veřejným klíčem, jako je šifra RSA, Diffie-Hellmanova výměna klíčů a šifra ElGamal, a řešení problému faktorizace celých čísel nebo diskrétního logaritmu. Existují numerické metody na řešení těchto problémů, nejefektivnější z nich jsou popsány v této práci. V případě řešení problému diskrétního logaritmu, jsou zde popsány metody jako Shankův baby-step giant-step algoritmus nebo metoda index calculus. Pro účely řešení problému faktorizace celých čísel jsou zde popsány metody jako Pollardova Rho metoda, Dixonova metoda náhodných čtverců, kvadratické síto a obecné číselné síto. Téma práce bylo řešeno vytvořením distribuované aplikace. Jedná se o kompozici webové a desktopové aplikace. Webová aplikace představuje řídící uzel distribuovaného systému. Pro uživatele je využitelná při správě úloh v systému. Poskytuje také základní funkcionalitu pro distribuci úloh podřízeným uzlům. Podřízené uzly jsou reprezentovány desktopovou aplikací. Jedná se o část, kde jsou implementovány popsané numerické metody pro řešení problému faktorizace čísel či diskrétního logaritmu. Nakonec je zde analýza použitelnosti distribuované aplikace pro reálné situace. Ta je složena z měření efektivity metod a jejich potenciálu v distribuované aplikaci. Ukázalo se, že distribuovaná aplikace představuje použitelný přístup pro řešení těchto typů problémů. Nicméně se také prokázalo, že pokud neudělá kryptograf žádnou chybu během implementace popsaných systémů, je téměř nemožné být úspěšný při kryptoanalýze těchto systémů. Práce analyzuje důležité téma související bezpečností dnes používaných kryptosystémů s veřejným klíčem. Toto téma je relevantní nejen pro vědecké účely, ale má také mnoho praktických konsekvencí.
Annotation in English
The thesis studies the potential of distributed application in cryptanalysis of public-key cryptosystems. There is an explanation of the relation among a popular public-key cryptosystems, such as RSA cypher, Diffie-Hellman key exchange and ElGamal cypher, and solving of integer factorization or discrete logarithm problem. There exists numerical methods for solving of these problems, the most effective ones are described in this thesis. In the case of solving discrete logarithm problems there are described method such as Shank's baby-step giant-step algorithm and Index calculus method. For the purpose of solving integer factorization problem there are described methods such as Pollard's rho method, Dixon's random square method, Quadratic Sieve and General number field sieve. The theme of the theses was solved by creating of distributed application. It is the composition of the web application and the desktop application. The web application represents master nod in the distributed system. It is usable for managing of task in the system for the users. It also provides basic functionality for distributing of the tasks to the slave nods. The slave nod is represented by the desktop application. It is the part where there are implemented described numerical methods for solving of integer factorization or discrete logarithm problem. Finally there is an analysis of usability of the distributed application for real situations. It consists of measurements of efficiency of methods and its potentials in distributed applications. It is shown that distributed application represents usable approach for solving of this kind of problems. However it is also shown that if cryptographers does not do any mistake during implementation of described cryptosystems, it is almost impossible to be successful with cryptanalysis of such system. The thesis analyzes important issue related with security of public-key cryptosystems of nowadays. This issue is relevant not only for scientific purposes but has also many practical consequences.
Keywords
Kryptoanalýza kryptosystémů s veřejným klíčem, Distribuovaná aplikace, Problém faktorizace čísel, Problém diskrétního logaritmu, Numerické metody
Primárním cílem je analyzovat potenciál distribuovaných systémů v kryptografických systémech s veřejným klíčem. Speciálně pak problému faktorizace velkých čísel a diskrétního logaritmu. Praktická část je zaměřena na vytvoření distribuované aplikace využívající vybrané algoritmy pro řešení těchto problémů.
Pokyny pro vypracování:
1. Popište vztah mezi diskrétním logaritmem, faktorizací celých čísel a moderními kryptografickými algoritmy s veřejným klíčem
2. Popište efektivní algoritmy pro řešení těchto problémů. Navrhněte strategii implementace těchto algoritmů v distribuovaných systémech.
3. Vytvořte distribuovanou aplikaci pro dešifrování zpráv zašifrovaných pomocí některých popsaných algoritmů využívajících veřejný klíč.
4. Analyzujte potenciál této aplikace v reálných situacích.
5. Práce bude vypracována v anglickém jazyce.
Research Plan
Primárním cílem je analyzovat potenciál distribuovaných systémů v kryptografických systémech s veřejným klíčem. Speciálně pak problému faktorizace velkých čísel a diskrétního logaritmu. Praktická část je zaměřena na vytvoření distribuované aplikace využívající vybrané algoritmy pro řešení těchto problémů.
Pokyny pro vypracování:
1. Popište vztah mezi diskrétním logaritmem, faktorizací celých čísel a moderními kryptografickými algoritmy s veřejným klíčem
2. Popište efektivní algoritmy pro řešení těchto problémů. Navrhněte strategii implementace těchto algoritmů v distribuovaných systémech.
3. Vytvořte distribuovanou aplikaci pro dešifrování zpráv zašifrovaných pomocí některých popsaných algoritmů využívajících veřejný klíč.
4. Analyzujte potenciál této aplikace v reálných situacích.
5. Práce bude vypracována v anglickém jazyce.
Recommended resources
[1] DELFS, Hans and Helmut KNEBL. Introduction to Cryptography: Principles and Applications. Third edition. Berlin: Springer, 2015.
[2] Y. YAN, Song, Moti YUNG and John RIEF. COMPUTATIONAL NUMBER THEORY AND MODERN CRYPTOGRAPHY. Higher Education Press: Singapore, 2013. ISBN 9781118188583.
Recommended resources
[1] DELFS, Hans and Helmut KNEBL. Introduction to Cryptography: Principles and Applications. Third edition. Berlin: Springer, 2015.
[2] Y. YAN, Song, Moti YUNG and John RIEF. COMPUTATIONAL NUMBER THEORY AND MODERN CRYPTOGRAPHY. Higher Education Press: Singapore, 2013. ISBN 9781118188583.
Týká se praxe
No
Enclosed appendices
1 CD
Appendices bound in thesis
-
Taken from the library
Yes
Full text of the thesis
Appendices
Reviewer's report
Supervisor's report
Defence procedure record
Defence procedure records are not shown to unauthorized users.
