JultikaUniversity of Oulu repository

Tiivistelmä

Tällä hetkellä käytössä olevat salausmenetelmät perustuvat pääosin vaikeisiin matemaattisiin ongelmiin, kuten kokonaisluvun tekijöihinjakoon ja diskreetin logaritmin ongelmaan. Kvanttitietokoneiden kehittyessä nämä salausmenetelmät saadaan kuitenkin helposti murrettua, joten uusien salausten kehittäminen on tärkeää. Erityisesti hiloihin perustuvia salausmenetelmiä pidetään lupaavina kvanttiturvallisuuden kannalta.

Selkäreppuongelmalla tarkoitetaan tilannetta, jossa on annettuna jono positiivisia kokonaislukuja ja jokin kokonaisluku S. Lukua S voidaan ajatella selkärepun tilavuutena ja jonon alkioita eri esineiden tilavuuksina. Tarkoituksena on valita jonosta sopivat esineet, joilla annettu selkäreppu saadaan tasan täyteen. Selkäreppuongelma on helppo ratkaista, jos annettuja esineitä on vähän, mutta se vaikeutuu huomattavasti, kun esineiden määrää kasvatetaan. Selkäreppuongelmaan perustuvia julkisen avaimen salausmenetelmiä kutsutaan selkäreppusalauksiksi. Merkle ja Hellman kehittivät ensimmäisen selkäreppusalauksen vuonna 1978. Sen toiminta perustui havaintoon, että selkäreppuongelma ratkeaa helposti, jos annettu jono on superkasvava. Pian kuitenkin huomattiin, että tämä salausmenetelmä on helppo murtaa esimerkiksi Shamirin hyökkäyksellä.

Merklen ja Hellmanin selkäreppusalausta voidaan kehittää p-adisia lukuja ja niiden approksimaatiohiloja käyttämällä. Näin rakennetut salausmenetelmät eroavat Merklen ja Hellmanin selkäreppusalauksesta siinä, että niissä salaisena avaimena käytettävä jono ei ole superkasvava, vaan vähenevä jono p-adisia lukuja. Salaovena näissä salauksissa käytetään p-adisella itseisarvolla toteutuvaa vahvaa kolmioepäyhtälöä. Tämän eroavaisuuden vuoksi p-adiset selkäreppusalaukset kestävät edellä mainitun Shamirin hyökkäyksen. Näille salauksille voidaan kuitenkin muodostaa muita hyökkäyksiä esimerkiksi LLL-algoritmia hyödyntämällä. LLL-hyökkäyksessä lasketaan hilalle redusoidut kantavektorit ja yritetään löytää niiden joukosta selkokielinen viesti. Yksinkertaisimmassa p-adisessa selkäreppusalauksessa LLL-hyökkäyksen rakentamiseen riittää salatun viestin paljastuminen hyökkääjälle.

Salauksen turvallisuutta voidaan kasvattaa lisäämällä viestin lähettäjälle yksi salainen avain enemmän. Tässä versiossa salattuun viestiin summataan yksi komponentti lisää, mikä vaikeuttaa LLL-hyökkäyksiä. Tällöin hyökkäyksen muodostamiseen ei riitä pelkkä salatun viestin paljastuminen, vaan lisäksi vaaditaan tietoa viestin lähettäjän salaisesta avaimesta tai selkokielisestä viestistä. Lisätyn avaimen avulla vastaanottaja pystyy myös varmistamaan viestin lähettäjän, mikä on merkittävä etu edelliseen selkäreppusalaukseen verrattuna. Salausten turvallisuutta voidaan lisätä kasvattamalla hilan dimensiota, koska tällöin LLL-hyökkäykset vaikeutuvat. Turvallisuuden rajana voidaan pitää hilan dimensiota 60.