Changeset 7282


Ignore:
Timestamp:
Feb 5, 2018, 7:35:48 PM (4 years ago)
Author:
krauss
Message:

LatticeCrypto documentation:

  • replaced special characters with their HTML symbol entities
  • </br> tag replaced with <br>
Location:
trunk/CrypPlugins/LatticeCrypto/OnlineHelp
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • trunk/CrypPlugins/LatticeCrypto/OnlineHelp/Start.en.htm

    r6122 r7282  
    2323
    2424   <p>
    25                 <strong>Lattices</strong></br>
     25                <strong>Lattices</strong><br>
    2626
    2727                A lattice consists of linearly independent vectors that are linearly combined with each other and thereby generate lattice points.
    2828                The difference between lattices and a &quot;normal&quot; vector space is the fact that the
    29                 vectors are multiplied with integer factors instead of real factors.</br>
     29                vectors are multiplied with integer factors instead of real factors.<br>
    3030
    3131                All the vectors form a so called basis for the lattice. This basis can be written in the form of a matrix.
    3232                The vectors can be written down in column notation, this is the most common way in papers. The vectors define so-called parallelepipeds, in the two-dimensional case these are parallelograms.
    33                 The volume of this parallelepiped is equal to the absolute value of the determinant.</br></br>
     33                The volume of this parallelepiped is equal to the absolute value of the determinant.<br><br>
    3434
    3535                Please note that in this crypto tutorial all values are integers,
     
    4040
    4141        <p>
    42                 <strong>Lattice problems</strong></br>
     42                <strong>Lattice problems</strong><br>
    4343
    4444                An important characteristic of lattices is the fact that they
     
    4646                have the same value. Regarding lattices, vectors with minimum length are
    4747                interesting. The problem to find these vectors is called the Shortest Vector
    48                 Problem (SVP) and relates to the search for "successive minima".</br>
     48                Problem (SVP) and relates to the search for "successive minima".<br>
    4949
    5050                The first minimum is the shortest vector. All other vectors are linearly independent to this and to each other, they are
     
    5353                Lattice point being as large as possible without overlapping each other
    5454                (both the Hermite circuit and the package circuits can be enabled in the settings).
    55                 It can be easily observed that after reduction the vectors are very much orthogonal to each other, ideally they even have the angle of 90 °.</br>
     55                It can be easily observed that after reduction the vectors are very much orthogonal to each other, ideally they even have the angle of 90&deg;.<br>
    5656
    5757                Another interesting problem is the Closest Vector Problem (CVP).
     
    6060
    6161        <p>
    62                 <strong>Lattice reduction</strong></br>
     62                <strong>Lattice reduction</strong><br>
    6363
    6464                There are two important methods that implement the search for shortest vectors. One of these is the Gaussian algorithm for dimension 2 and secondly the LLL algorithm, named after
    65                 Arjen Lenstra, Hendrik Lenstra and László Lovász, for an arbitrary lattice dimension.
     65                Arjen Lenstra, Hendrik Lenstra and L&aacute;szl&oacute; Lov&aacute;sz, for an arbitrary lattice dimension.
    6666                The Gaussian algorithm works similar to the Euclidean algorithm for searching
    6767                the greatest common divisor (gcd) of two integers. By combining and subtracting of two vectors the basis&nbsp;improves after each iteration with a shorter vector.
     
    7272
    7373        <p align="justify">
    74                 <strong>Cryptanalysis</strong></br>
     74                <strong>Cryptanalysis</strong><br>
    7575
    7676                After the publication of the LLL algorithm in 1982, many possible applications were found for it, cryptanalysis being one of them.
    7777                The Merkle-Hellman knapsack cryptosystem, designed in 1978 and named after its two inventors Ralph C. Merkle and Martin E. Hellman, could impressively be broken with the help of lattices.
    7878                This cryptosystem is based on the knapsack problem, for which a general solution is difficult to find.
    79                 But it could be demonstrated, that the problem of decrypting a ciphertext can be reformulated as a search for a shortest vector.</br>
     79                But it could be demonstrated, that the problem of decrypting a ciphertext can be reformulated as a search for a shortest vector.<br>
    8080
    8181                The well-known asymmetric encryption scheme RSA (named after its inventors Ronald L. Rivest, Adi Shamir and Leonard Adleman) was developed at about the same time as the Merkle-Hellman cryptosystem.
     
    8484                The messages in this case are so called "stereotypical messages", for example "Your new PIN is: ****".
    8585                The first part of the messages, which is always the same, must be known to the attacker.
    86                 A prerequisite for this attack is that the public exponent e is very small, for example 3.</br>
     86                A prerequisite for this attack is that the public exponent e is very small, for example 3.<br>
    8787
    8888                Another attack scenario that uses lattices involves a partially known private key.
     
    9191
    9292    <p align="justify">
    93                 <strong>Lattice-based cryptosystems</strong></br>
     93                <strong>Lattice-based cryptosystems</strong><br>
    9494
    9595                Cryptosystems that are based on lattices exploit the hardness of certain lattice problems, in particular the Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP).
    96                 As in the case of RSA, these cryptosystems are asymmetric public-key cryptosystems.</br>
     96                As in the case of RSA, these cryptosystems are asymmetric public-key cryptosystems.<br>
    9797
    9898                The foundations for lattice-based cryptography were laid by Miklos Ajtai in 1986, when he demonstrated how lattices could be used for cryptography.
     
    101101                The security of GGH is based on the hardness of CVP.
    102102                GGH can also be used to generate electronic signatures.
    103                 Both cryptosystems, Ajtai-Dwork and GGH, were successfully attacked and broken.</br>
     103                Both cryptosystems, Ajtai-Dwork and GGH, were successfully attacked and broken.<br>
    104104
    105105                The cryptosystem NTRU (Number Theory Research Unit) was presented by Jeffrey Hoffstein, Jill Pipher and Joseph H. Silverman in 1998.
    106106                It can encrypt (NTRUEncrypt) as well as create electronic signatures (NTRUSign). The security of NTRU relies on the hardness of SVP.
    107                 The advantages of NTRU are the fast encryption and decryption speed and the fact that, unlike in the case of RSA, no quantum algorithm for attacking it in polynomial time is as yet known.</br>
     107                The advantages of NTRU are the fast encryption and decryption speed and the fact that, unlike in the case of RSA, no quantum algorithm for attacking it in polynomial time is as yet known.<br>
    108108
    109109                The latest lattice-based cryptosystem is <i>Learning With Errors</i> (LWE), which was published by Oded Regev in 2005.
    110                 It too is based on hard lattice problems, like SVP.</br>
     110                It too is based on hard lattice problems, like SVP.<br>
    111111
    112112                Compared to established public-key cryptosystems like RSA, lattice-based cryptosystems have to handle larger key sizes and also larger ciphertexts.
  • trunk/CrypPlugins/LatticeCrypto/OnlineHelp/Start.htm

    r6045 r7282  
    2020    </p>
    2121    <p>
    22         <strong>Gitter</strong></br> Ein Gitter besteht aus linear unabhängigen Vektoren, die miteinander linear kombiniert werden,
     22        <strong>Gitter</strong><br> Ein Gitter besteht aus linear unabhängigen Vektoren, die miteinander linear kombiniert werden,
    2323        und dadurch Gitterpunkte erzeugen. Der Unterschied zwischen Gittern und einem "normalen" Vektorraum besteht
    24         darin, dass die Vektoren ganzzahlig kombiniert werden.</br>
     24        darin, dass die Vektoren ganzzahlig kombiniert werden.<br>
    2525        Nimmt man alle Vektoren zusammen, bezeichnet man diese als Basis für das Gitter. Diese Basis kann auch in
    2626        Form einer Matrix aufgeschrieben werden. Die Vektoren können z.B. in Spaltenschreibweise
    2727        aufgeschrieben werden. Die Vektoren spannen so genannte Parallelepipede auf, im zwei-dimensionalen Fall sind dies Parallelogramme.
    2828        Das Volumen dieses Parallelepipeds ist gleich dem Absolutbetrag der Determinante.
    29         </br></br>
     29        <br><br>
    3030        Beachten Sie bitte, dass in diesem Kryptotutorial alle Werte ganzzahlig sind. Dies ist keine Voraussetzung
    3131        für Gitter. Da aber in der Kryptographie häufig mit großen Ganzzahlen gerechnet wird, werden auch hier
     
    3434    </p>
    3535    <p>
    36         <strong>Gitterprobleme</strong></br> Eine wichtige Eigenschaft von Gittern ist, dass sie
     36        <strong>Gitterprobleme</strong><br> Eine wichtige Eigenschaft von Gittern ist, dass sie
    3737        verschiedene Basen haben können, die alle das gleiche  Gitter erzeugen. Diese Basen haben dann auch
    3838        alle die gleiche Gitterdeterminante. Im Zusammenhang mit Gittern sind aber vor allem solche Vektoren interessant,
    3939        die eine minimale Länge besitzen. Dieses Problem wird Shortest Vector Problem (SVP) genannt.
    40         Gesucht werden dabei die so genannten "Sukzessiven Minima".</br>
     40        Gesucht werden dabei die so genannten "Sukzessiven Minima".<br>
    4141        Das erste Minimum ist dabei der kürzeste Vektor. Alle weiteren sind dazu linear unabhängig und wiederum
    4242        so kurz wie möglich. Eine obere Schranke für den kürzesten Vektor wird durch die Hermite-Konstante. Der
     
    4545        (sowohl der Hermite-Kreis als auch die Packungskreise können in den Einstellungen freigeschaltet werden).
    4646        Es lässt sich gut beobachten, dass die Vektoren nach einer Reduktion sehr viel orthogonaler zueinander sind,
    47         im Idealfall haben sie sogar den Winkel 90°.</br>
     47        im Idealfall haben sie sogar den Winkel 90&deg;.<br>
    4848        Ein weiteres interessantes Problem ist das Closest Vector Problem (CVP). Hier wird ein beliebiger Punkt
    4949        vorgegeben und es soll ein Gitterpunkt gesucht werden, der diesem Punkt am nächsten ist.
    5050    </p>
    5151    <p>
    52         <strong>Gitterreduktion</strong></br> Es gibt zwei wichtige Verfahren, welche die Suche nach
     52        <strong>Gitterreduktion</strong><br> Es gibt zwei wichtige Verfahren, welche die Suche nach
    5353        kürzesten Vektoren realisieren. Zum einen ist dies der Gauß-Algorithmus für die Dimension 2 und
    54         zum anderen der LLL-Algorithmus, benannt nach Arjen Lenstra, Hendrik Lenstra und László Lovász,
    55         für eine beliebige Gitterdimension.</br>
     54        zum anderen der LLL-Algorithmus, benannt nach Arjen Lenstra, Hendrik Lenstra und L&aacute;szl&oacute; Lov&aacute;sz,
     55        für eine beliebige Gitterdimension.<br>
    5656        Der Gauß-Algorithmus arbeitet ähnlich dem euklidischen Algorithmus zur Suche des größten gemeinsamen Teilers
    5757        (ggT) zweier ganzer Zahlen. Durch Kombination und Subtraktion der beiden Vektoren
     
    6060        aber nur
    6161        noch eine Approximation (Annäherung) an den kürzesten Vektor. Ein wichtiger Bestandteil des
    62         Algorithmus ist die Gram-Schmidt-Orthogonalisierung.</br>
     62        Algorithmus ist die Gram-Schmidt-Orthogonalisierung.<br>
    6363    </p>
    6464    <p align="justify">
    65         <strong>Kryptoanalyse</strong></br> Nachdem der LLL-Algorithmus 1982 veröffentlicht wurde,
     65        <strong>Kryptoanalyse</strong><br> Nachdem der LLL-Algorithmus 1982 veröffentlicht wurde,
    6666        fanden sich zahlreiche Einsatzmöglichkeiten, unter anderem in der Kryptoanalyse. So wurde das
    6767        von Ralph C. Merkle und Martin E. Hellman 1978 entwickelte und nach ihnen benannte Kryptosystem
     
    6969        dem Rucksackproblem, welches im Allgemeinen sehr schwer zu lösen ist. Im Konkreten zeigte sich jedoch,
    7070        dass das Entschlüsseln einer Chiffre in Kombination mit dem öffentlichen Schlüssel als Suche nach einem kürzesten Vektor
    71         umformuliert werden konnte.</br>
     71        umformuliert werden konnte.<br>
    7272        Das bekannteste, asymmetrische Verschlüsselungsverfahren RSA, benannt nach Ronald L. Rivest, Adi Shamir und Leonard Adleman,
    7373        wurde etwa zur gleichen Zeit wie das von Merkle und Hellman entwickelt. Es basiert auf dem Problem der Primfaktorzerlegung von großen Zahlen.
     
    7575        der Nachricht bekannt ist, entschlüsselt werden können. Diese Nachrichten sind so genannte "stereotype Nachrichten",
    7676        wie z.B. "Ihre neue PIN lautet: ****". Der erste Teil der Nachricht kann immer gleich sein und daher dem Angreifer bekannt.
    77         Voraussetzung für den Angriff ist, dass der öffentliche Exponent e sehr klein ist, z.B. 3.</br>
     77        Voraussetzung für den Angriff ist, dass der öffentliche Exponent e sehr klein ist, z.B. 3.<br>
    7878        Eine weitere Angriffsmöglichkeit ist ein teilweise bekannter privater Schlüssel. Auch hier kann mithilfe von Gittern ein Angriff gestartet werden.
    7979        Im Gegensatz zum Merkle-Hellman-Kryptosystem konnte das RSA-Verfahren nicht gebrochen werden und gilt daher (mit einigen
     
    8181    </p>
    8282    <p align="justify">
    83         <strong>Gitterbasierte Kryptosysteme</strong></br>
    84         Kryptosysteme, die auf Basis von Gittern arbeiten, machen sich die Gitterprobleme, im Besonderen, Shortest Vector Problem (SVP) und Closest Vector Problem (CVP), zunutze. Es handelt sich hierbei, wie bei RSA, um asymmetrische Public-Key-Kryptosysteme.</br>
     83        <strong>Gitterbasierte Kryptosysteme</strong><br>
     84        Kryptosysteme, die auf Basis von Gittern arbeiten, machen sich die Gitterprobleme, im Besonderen, Shortest Vector Problem (SVP) und Closest Vector Problem (CVP), zunutze. Es handelt sich hierbei, wie bei RSA, um asymmetrische Public-Key-Kryptosysteme.<br>
    8585        Die Grundlagen für die gitterbasierte Kryptographie wurden 1996 von Miklos Ajtai
    8686        geschaffen, indem er aufzeigte, wie Gitter für die Kryptographie genutzt werden
     
    9292        Schwierigkeit das CVP zu lösen. Es war außerdem möglich, Nachrichten mithilfe
    9393        des GGH-Signaturverfahren zu signieren. Beide Kryptosysteme, sowohl Ajtai-Dwork
    94         als auch GGH, wurden erfolgreich angegriffen und gebrochen.</br>
    95 Das Kryptosystem NTRU (als Abkürzung von &quot;Number Theory Research Unit&quot;) wurde 1998 von Jeffrey Hoffstein, Jill Pipher und Joseph H. Silverman vorgestellt. Es sind sowohl Verschlüsselungen (NTRUEncrypt) als auch elektronische Signaturen (NTRUSign) möglich. Die Sicherheit von NTRU liegt im Lösen des SVP. Als Besonderheit gilt zum einen die schnelle Ver- und Entschlüsselung und zum anderen der Umstand, dass (im Gegensatz zu RSA) bisher noch kein Quantenalgorithmus bekannt ist, der NTRU in Polynomialzeit bricht.</br>
    96         Das neueste, gitterbasierte Kryptosystem ist Learning with Errors (kurz LWE), welches von Oded Regev in 2005 veröffentlicht wurde. Es basiert ebenfalls auf schwer zu lösenden Gitterproblemen, wie dem SVP.</br>
     94        als auch GGH, wurden erfolgreich angegriffen und gebrochen.<br>
     95Das Kryptosystem NTRU (als Abkürzung von &quot;Number Theory Research Unit&quot;) wurde 1998 von Jeffrey Hoffstein, Jill Pipher und Joseph H. Silverman vorgestellt. Es sind sowohl Verschlüsselungen (NTRUEncrypt) als auch elektronische Signaturen (NTRUSign) möglich. Die Sicherheit von NTRU liegt im Lösen des SVP. Als Besonderheit gilt zum einen die schnelle Ver- und Entschlüsselung und zum anderen der Umstand, dass (im Gegensatz zu RSA) bisher noch kein Quantenalgorithmus bekannt ist, der NTRU in Polynomialzeit bricht.<br>
     96        Das neueste, gitterbasierte Kryptosystem ist Learning with Errors (kurz LWE), welches von Oded Regev in 2005 veröffentlicht wurde. Es basiert ebenfalls auf schwer zu lösenden Gitterproblemen, wie dem SVP.<br>
    9797Im Vergleich zu etablierten Public-Key-Verfahren wie RSA haben gitterbasierte Kryptosysteme häufig mit längeren Schlüssellängen und auch größeren Chiffren zu kämpfen. Dagegen haben sie oft den Vorteil, dass sie schneller sind und im Gegensatz zu RSA (noch) nicht durch den Einsatz von Quantencomputern angreifbar sind.
    9898    </p>
Note: See TracChangeset for help on using the changeset viewer.