Hash functions and combinatorics on words

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21340%2F13%3A00210021" target="_blank" >RIV/68407700:21340/13:00210021 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

čeština

Original language name

Hašovací funkce a kombinatorika na slovech

Original language description

Hašovací funkce jsou zázračné funkce, které z dlouhých zpráv vyrábějí jejich krátké otisky (anglicky hash). Chovají se jako tzv. náhodná orákula, tedy otisky jsou jakoby náhodně losovány. Dále musí být funkce jednocestné, tj. musí splňovat, že hašování,tedy získávání otisku zprávy, je rychlé, zatímco k danému otisku je výpočetně nemožné najít zprávu, která by měla tento otisk. Podle konkrétní aplikace pak klademe na hašovací funkce ještě další požadavky. Ukazuje se, že iterativní princip, na kterém jevětšina současných hašovacích funkcí založena, není dostatečně silný proti útoku na druhý vzor a multikolize. Ronald Rivest navrhl jako jedno z řešení metodu ditherování. V~článku se zabýváme studiem jejích výhod a nevýhod a využíváme výsledků z kombinatoriky na slovech pro konstrukci vhodných ditheračních posloupností. Na závěr se ještě krátce zmíníme o výsledcích soutěže o nový hašovací standard SHA-3, kterým se 2. října 2012 stal algoritmus Keccak.

Czech name

Hašovací funkce a kombinatorika na slovech

Czech description

Hašovací funkce jsou zázračné funkce, které z dlouhých zpráv vyrábějí jejich krátké otisky (anglicky hash). Chovají se jako tzv. náhodná orákula, tedy otisky jsou jakoby náhodně losovány. Dále musí být funkce jednocestné, tj. musí splňovat, že hašování,tedy získávání otisku zprávy, je rychlé, zatímco k danému otisku je výpočetně nemožné najít zprávu, která by měla tento otisk. Podle konkrétní aplikace pak klademe na hašovací funkce ještě další požadavky. Ukazuje se, že iterativní princip, na kterém jevětšina současných hašovacích funkcí založena, není dostatečně silný proti útoku na druhý vzor a multikolize. Ronald Rivest navrhl jako jedno z řešení metodu ditherování. V~článku se zabýváme studiem jejích výhod a nevýhod a využíváme výsledků z kombinatoriky na slovech pro konstrukci vhodných ditheračních posloupností. Na závěr se ještě krátce zmíníme o výsledcích soutěže o nový hašovací standard SHA-3, kterým se 2. října 2012 stal algoritmus Keccak.

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

BA - General mathematics

OECD FORD branch

—

Project

<a href="/en/project/GA13-03538S" target="_blank" >GA13-03538S: Algorithms, Dynamics and Geometry of Numeration systems</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2013

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Pokroky matematiky, fyziky a astronomie

ISSN

0032-2423

e-ISSN

—

Volume of the periodical

58

Issue of the periodical within the volume

4

Country of publishing house

CZ - CZECH REPUBLIC

Number of pages

11

Pages from-to

274-284

UT code for WoS article

—

EID of the result in the Scopus database

—