| Identifikační kód |
RIV/67985807:_____/10:00351385 |
| Název v anglickém jazyce |
Remarks on Gödel's Code as a Hash Function |
| Druh |
J - Recenzovaný odborný článek (Jimp, Jsc a Jost) |
| Poddruh |
- |
| Jazyk |
eng - angličtina |
| Obor - skupina |
B - Fyzika a matematika |
| Obor |
BA - Obecná matematika |
| Rok uplatnění |
2010 |
| Kód důvěrnosti údajů |
S - Úplné a pravdivé údaje o výsledku nepodléhající ochraně podle zvláštních právních předpisů. |
| Počet výskytů výsledku |
2 |
| Počet tvůrců celkem |
2 |
| Počet domácích tvůrců |
1 |
| Výčet všech uvedených jednotlivých tvůrců |
Petr Savický (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 3559491)
M. Mikuš (státní příslušnost: SK - Slovenská republika) |
| Popis výsledku v anglickém jazyce |
In this paper we analyze a simple hash function introduced in a popular book PopCo by Scarlett Thomas that is based on well known Gödel's numbering function. The numbering function is very slow for practical use, however it is widely used in foundationsof logic and computability theory. We show that the properties of the suggested hash function (computing the hash as a "shorter digest" of the long Gödel's number code) are not sufficient for cryptography. We introduce two ways how to construct meaningful collisions and in special cases also second-preimages. Further we propose a simple improvement of this hash function which prevents the simpler of the attacks, however this hasn't been successful for the second attack. |
| Klíčová slova oddělená středníkem |
Gödel numbering function; hash function; rational reconstruction; integer relation algorithm |
| Stránka www, na které se nachází výsledek |
http://www.sav.sk/journals/uploads/0317151904m-s.pdf |
| Odkaz na údaje z výzkumu |
- |