Gitterreduktionsdemonstration

Forstå gitterreduktion med et konkret eksempel

Antag, at du vil finde den korteste vektor i et gitter udspændt af vektorerne v1 = (2, 3) og v2 = (4, 5). Med et koefficientområde på 10 vil værktøjet undersøge alle kombinationer af i og j fra -10 til 10 (undtagen i=j=0). For hvert par beregnes vektoren i*v1 + j*v2, og længden kvadreret sammenlignes. I dette tilfælde finder værktøjet vektoren (-2, -2) med koefficientpar (i=1, j=-1), fordi 1*(2,3) + (-1)*(4,5) = (-2, -2). Længden er ca. 2,82843.

Vigtige parametre og begrænsninger

• Basisvektorerne skal være lineært uafhængige, ellers er gitteret ikke todimensionalt.
• Koefficientområdet er et heltal mellem 1 og 100. Jo større område, desto flere kombinationer undersøges, men beregningstiden stiger tilsvarende.
• Værktøjet finder kun den korteste vektor inden for det valgte søgevindue. En vektor uden for vinduet kan være kortere.
• Hvis flere vektorer har samme længde, vises kun én af dem.

Ofte stillede spørgsmål

Hvordan afrundes længden?

Længden afrundes til fem decimaler. For eksempel vises 2,8284271247 som 2,82843.

Hvorfor er resultatet ikke altid den globale korteste vektor?

Fordi søgningen er begrænset til det valgte koefficientområde. Hvis den sande korteste vektor kræver en koefficient uden for området, finder værktøjet den ikke. Øg området for at få et mere dækkende resultat.

Kan værktøjet bruges til at vurdere sikkerheden af rigtige kryptografiske systemer?

Nej. Dette er et pædagogisk værktøj til todimensionale gitre. Det udfører ikke LLL, BKZ eller anden avanceret kryptanalyse og bør ikke bruges til at bedømme sikkerheden af faktiske kryptografiske parametre.