WikiDer > Indexberechnungsalgorithmus

In dem Gruppentheorie, Teil von dem Mathematik, ist der Indexberechnungsalgorithmus ein Algorithmus für einige Gruppen das diskreter Logarithmus, h = g^nein, zu lösen, wo G und haElemente aus der Gruppe, G, sein. Ein diskreter Logarithmus ist auf a . definiert endliche Gruppe G. Vorher G wenn Urheber von G und h ${Anzeigestil in }$ G geht auf die Lösung von ${Anzeigestil h=g^{n}}$ fragte.

Der Algorithmus

Der Indexberechnungsalgorithmus kann angewendet werden auf endliche Felder.

Die Methode für Primkörper${displaystyle mathbb {F} }$${displaystyle _{p}}$ und binäre Felder${displaystyle mathbb {F} _{2^{m}}}$ lässt sich wie folgt beschreiben:

In Primkörpern

${displaystyle langle}$G${Anzeigestilwinkel}$ ist ein Untergruppe von ${displaystyle mathbb {F} _{p}^{*}}$, huh ${Anzeigestil in }$${displaystyle langle}$G${Anzeigestilwinkel}$
wofür nein ${Anzeigestil in Mathbb {Z} }$ gilt ${Anzeigestil h=g^{n}}$ (mod p)

Der Algorithmus verwendet eine Faktorbasis von mehreren kleinen Primzahlen, B={ (-1), 2, 3, 5, 7,..., r}

Schritt 1:
Finde etwas Elemente von ${displaystyle langle}$G${Anzeigestilwinkel}$ die die Eigenschaft haben, auch zu sein in Primfaktoren zerlegen von dem Sammlung b.
Wir schreiben diese Gruppenelemente als ${displaystyle g^{r_{i}}=(-1)^{e_{1}}cdot p_{2}^{e_{2}}cdot dots cdot p_{k}^{e_{k}}}$

Schritt 2:
Nimm den Logarithmus auf beiden Seiten. Dadurch entsteht ein lineares Gleichungssystem woraus die diskrete Logarithmen der verwendeten Primzahlen gelöst werden.

Schritt 3:
Dann suche nach einem Element ${displaystyle g^{i}}$ damit er ${displaystyle cdot }$${displaystyle g^{i}}$ kann mit Primfaktoren aus B aufgelöst werden.
ha ${displaystyle cdot }$ (G${displaystyle ^{r_{i}}}$) = (-1)${displaystyle ^{e_{1}}}$${displaystyle cdot }$${displaystyle p_{2}}$${displaystyle ^{e_{2}}}$${displaystyle cdot }$ ... ${displaystyle cdot }$${displaystyle p_{k}}$${displaystyle ^{e_{k}}}$
Durch den Logarithmus auf beiden Seiten erhält man den Wert von n.
Die drei Schritte des Algorithmus wurden mit Hilfe des folgenden Beispiels erarbeitet.

In binären Feldern

Die Elemente des endlichen Körpers ${displaystyle mathbb {F} _{2^{m}}}$ werden als Polynome in . dargestellt ${displaystyle mathbb {F} }$${displaystyle _{2}}$[x] mit einem Grad von höchstens (m-1). Die Operation ist Multiplikation modulo ein festes Polynom vom Grad n, f(x) in ${displaystyle mathbb {F} }$${displaystyle _{2}}$[x], das nicht aufgelöst werden kann.
Wählen Sie für die Faktorbasis B Elemente aus der Menge aller nicht zerlegbaren Polynome in ${displaystyle mathbb {F} }$${displaystyle _{2}}$[x] mit einem Grad von nicht mehr als einer vorbestimmten Obergrenze.

Schritt 1:
Polynome suchen ${displaystyle g^{k}}$ mod f(x), mit g als Generator von ${displaystyle mathbb {F} _{2^{m}}}$ die ein Produkt von Polynomen aus B sind.

Schritt 2:
Genau wie bei Primkörpern können die Logarithmen der Polynome durch Lösen eines Gleichungssystems ermittelt werden.

Schritt 3: Suchen Sie als Nächstes nach einem Polynom ${displaystyle g^{i}}$ damit er ${displaystyle cdot }$${displaystyle g^{i}}$ kann mit Polynomen aus B aufgelöst werden.
Durch den Logarithmus auf beiden Seiten erhält man den Wert von n.

Beispiele

In Primkörpern

Wir nehmen an ${displaystyle mathbb {F}_{2003}^{*}}$= ${displaystyle langle}$5${Anzeigestilwinkel}$ mit p=2003.
Wir wählen nun h = 543 aus dieser Gruppe und wollen nach n aus h = . auflösen ${Displaystil 5^{n}}$ Mod 2003.

Schritt 1:
Nehmen Sie B = {(-1), 2, 3, 5, 7, 11, 13, 19}. Dies ist eine kleine Faktorbasis.
Der Nachteil dabei ist, dass Sie länger nach Zahlen suchen müssen, die damit faktorisiert werden können, der Vorteil ist, dass das zu lösende System in der Größe begrenzt ist.
Wir wählen jetzt zufällig Zahlen aus getallen ${displaystyle langle}$5${Anzeigestilwinkel}$ und faktoriere sie in Primzahlen. Wir können nur Zahlen verwenden, die mit B faktorisiert werden können.

964 = ${Displaystil 2^{2}}$${displaystyle cdot }$${displaystyle 241^{1}}$
wir werden nicht verwenden.

Nach ein paar Versuchen haben wir:

${displaystyle { egin{matrix}5^{37}&=&2^{3}&cdot &13^{1}&cdot &19^{1}/5^{37}&=&(-1)^{1}&cdot &3 ^{3}&&&/5^{1998}&=&2^{1}&cdot &7^{1}&cdot &19^{1}/5^{21}&=&2^{9}&&&&/5^{108} &=&(-1)^{1}&cdot &7^{1}&cdot &13^{2}end{array}}}$

Jede Primzahl kommt mindestens zweimal vor. Wir schreiben nun die erste Gleichung wie folgt:

${Anzeigestil ^{5}}$Log ${Displaystil 5^{37}}$ = ${Anzeigestil ^{5}}$log (${Displaystil 2^{3}}$${displaystyle cdot }$${Displaystil 13^{1}}$${displaystyle cdot }$${Displaystil 19^{1}}$) = ${Anzeigestil ^{5}}$Log ${Displaystil 2^{3}}$${Anzeigestil ^{5}}$log13 ${Anzeigestil ^{5}}$log19
37 = 3 ${displaystyle cdot }$${Anzeigestil ^{5}}$log2 1 ${displaystyle cdot }$${Anzeigestil ^{5}}$log13 1 ${displaystyle cdot }$${Anzeigestil ^{5}}$log19

Für 108 gilt:
108 = 1 ${displaystyle cdot }$${Anzeigestil ^{5}}$log(-1) 1 ${displaystyle cdot }$${Anzeigestil ^{5}}$log7 2 ${displaystyle cdot }$${Anzeigestil ^{5}}$log13

weil ${Displaystil 5^{2002}}$ = 1 und so (${Displaystil 5^{1001}}$)${Anzeigestil ^{2}}$ = 1, muss das halten ${Displaystil 5^{1001}}$ = -1 (mod 2002). Jedes Element von ${displaystyle langle}$5${Anzeigestilwinkel}$ ist doch einzigartig.
Deshalb wissen wir das
108 = 1001 1 ${displaystyle cdot }$${Anzeigestil ^{5}}$log7 2 ${displaystyle cdot }$${Anzeigestil ^{5}}$log13

Schritt 2:
Wir wollen nun den Wert der verwendeten Logarithmen wissen. Wir finden es, indem wir die folgende Matrix verwenden.

${displaystyle { egin{matrix}^{5}log 2&^{5}log 7&^{5}log 13&^{5}log 19&/3&0&1&1&37/1&1&0&1&1998/0&1&2&0&1109/9&0&0&0&21end{matrix}}}$

In der unteren Reihe durch 9 teilen.
21 steht für eine Zahl (21 k ${displaystyle cdot }$ 2002)
Für k = 6 ergibt dies 12033, was durch 9 teilbar ist.
Jetzt wissen wir das
${Anzeigestil ^{5}}$log2 = 1337 (mod 2002).

${displaystyle { egin{matrix}^{5}log 2&^{5}log 7&^{5}log 13&^{5}log 19&/0&0&1&1&37-3cdot 1337=30/0&1&0&1&1998-1337=661/0&1&2&0&1109/1&0&0&0&1337end{matrix }}}$

${displaystyle { egin{matrix}^{5}log 7&^{5}log 13&^{5}log 19&/0&1&1&30/1&0&1&661/1&2&0&1109end{matrix}}}$

${displaystyle { egin{matrix}^{5}log 7&^{5}log 13&^{5}log 19&/0&1&1&30/1&-1&0&661-30=631/1&2&0&1109end{matrix}}}$

${displaystyle { egin{matrix}^{5}log 7&^{5}log 13&^{5}log 19&/0&1&1&30/1&-1&0&631/3&0&0&1109 2cdot 631=369end{matrix}}}$

Jetzt folgt ${Anzeigestil ^{5}}$log7 = 123 (mod 2002)
${Anzeigestil ^{5}}$log13 = 123 - 631 1494 (mod 2002)
${Anzeigestil ^{5}}$log19 = 30 - 1494 = 538 (mod 2002)

Schritt 3:
Wir suchen nun nach einer geeigneten Faktorisierung von Zahlen der folgenden Form: 543 ${displaystyle cdot }$${Displaystil 5^{i}}$
Nach ein paar Versuchen haben wir

543 ${displaystyle cdot }$${Displaystil 5^{433}}$ = (-1) ${displaystyle cdot }$${Displaystil 2^{2}}$${displaystyle cdot }$${Displaystil 19^{2}}$

Daraus folgt die Gleichung

${Anzeigestil ^{5}}$log 543 ${displaystyle cdot }$${Displaystil 5^{433}}$ = ${Anzeigestil ^{5}}$log(-1) 2 ${displaystyle cdot }$${Anzeigestil ^{5}}$log2 2 ${displaystyle cdot }$${Anzeigestil ^{5}}$log19
${Anzeigestil ^{5}}$log 543 433 = 1001 2 ${displaystyle cdot }$ 1337 2 ${displaystyle cdot }$ 538

Daraus folgt ${Anzeigestil ^{5}}$log 543 = 314,
die Lösung: n = 314

In binären Feldern

Wir nehmen an ${displaystyle mathbb {F} _{2^{7}}}$ mod f(x) = ${Anzeigestil x^{7}}$ x 1
Die Elemente von ${displaystyle mathbb {F} _{2^{7}}}$ sind alle Polynome in ${displaystyle mathbb {F} }$${displaystyle _{2}}$ höchstens Grades 6. Die Operation ist Multiplikation mod f(x). Die Reihenfolge von ${displaystyle mathbb {F} _{2^{7}}}$ ist 128 - 1 = 127
Das Polynom g = x ist Generator von ${displaystyle mathbb {F} _{2^{7}}}$
Wir wählen nun h = ${Anzeigestil x^{4}}$${Anzeigestil x^{3}}$${Displaystil x^{2}}$ x 1 aus dieser Gruppe und wollen nach n aus auflösen
${Anzeigestil x^{4}}$${Anzeigestil x^{3}}$${Displaystil x^{2}}$ x 1 =${Displaystil x^{n}}$ mod f(x)

Schritt 1:
Wähle als Faktorbasis die Menge aller nicht zerlegbaren Polynome in ${displaystyle mathbb {F} }$${displaystyle _{2}}$[x] höchstens Grades 3.
B = {x,x1, ${Displaystil x^{2}}$ x 1, ${Anzeigestil x^{3}}$ x 1, ${Anzeigestil x^{3}}$${Displaystil x^{2}}$ 1}
Suchen Sie nun nach Polynomen, die mit Polynomen aus B faktorisiert werden können. Unten sind fünf erfolgreich.

${displaystyle { egin{matrix}x^{18}&{ mod {f}}(x)&=&x^{6} x^{4}&=&x^{4}(x 1)^{2}/ x^{105}&{ mod {f}}(x)&=&x^{6} x^{5} x^{4} x&=&x(x 1)^{2}(x^{3} x ^{2} 1)/x^{72}&{ mod {f}}(x)&=&x^{6} x^{5} x^{3} x^{2}&=&x^{2 }(x 1)^{2}(x^{2} x 1)/x^{45}&{ mod {f}}(x)&=&x^{5} x^{2} x 1&=& (x 1)^{2}(x^{3} x 1)/x^{121}&{mod {f}}(x)&=&x^{6} x^{5} x^{4} x^{3} x^{2} x 1&=&(x^{3} x 1)(x^{3} x^{2} 1)Ende{Array}}}$

Schritt 2:
Wir wollen nun den Wert der verwendeten Logarithmen wissen.
Paar

${displaystyle { egin{matrix}p_{1}&=&^{x}log x/p_{2}&=&^{x}log(x 1)/p_{3}&=&^{x}log (x^{2} x 1)/p_{4}&=&^{x}log(x^{3} x 1)/p_{5}&=&^{x}log(x^{3} x^{2} 1)Ende{array}}}$

Das gibt

${displaystyle { egin{matrix}18&=&4p_{1} 2p_{2}&{ mod {1}}27/105&=&p_{1} 2p_{2} p_{5}&{ mod {1}}27/72& =&2p_{1} 2p_{2} p_{3}&{ mod {1}}27/45&=&2p_{2} p_{4}&{ mod {1}}27/121&=&p_{4} p_{5 }&{ mod {1}}27end{array}}}$

weil ${displaystyle p_{1}}$ = 1 kann dies vereinfacht werden zu

${displaystyle { egin{matrix}14&=&2p_{2}&{ mod {1}}27/104&=&2p_{2} p_{5}&{ mod {1}}27/70&=&2p_{2} p_{3 }&{ mod {1}}27/45&=&2p_{2} p_{4}&{ mod {1}}27/121&=&p_{4} p_{5}&{ mod {1}}27end{matrix} }}$

Daraus folgt ${displaystyle p_{2}}$ = 7, also ${displaystyle p_{5}}$ = 90, ${displaystyle p_{3}}$ = 56 und ${displaystyle p_{4}}$ = 31

Schritt 3:
Wir suchen nun nach einer geeigneten Zerlegung von Polynomen der Form h ${displaystyle cdot }$${Displaystil x^{i}}$ mod f(x), die mit Polynomen aus B faktorisiert werden können.
Das funktioniert für i = 66
(${Anzeigestil x^{4}}$${Anzeigestil x^{3}}$${Displaystil x^{2}}$ x1) ${Anzeigestil x^{66}}$ mod f(x) = ${Anzeigestil x^{5}}$${Anzeigestil x^{3}}$ x = x(${Displaystil x^{2}}$ x1)${Anzeigestil ^{2}}$
So ${Anzeigestil ^{x}}$Log(${Anzeigestil x^{4}}$${Anzeigestil x^{3}}$${Displaystil x^{2}}$ x1) = ( ${displaystyle p_{1}}$ 2 ${displaystyle cdot }$${displaystyle p_{3}}$ -66) (mod 127) = 47
die Lösung: n = 47

Siehe auch

• Baby Schritte Riesenschritte Algorithmus
• Pohlig-Hellman-Algorithmus
• Lambda-Algorithmus von Pollardard
• Der Rho-Algorithmus von Pollard

Verweise

• (und) Alfred J. Menezes, Paul C. van Oorschot und Scott A. Vanstone, Handbuch der angewandten Kryptographie, 2001.
• (und) DJ Bernstein, Generische Angriffe und Indexkalküle , Universität von Illinois, Chicago.
• (und) Neal Koblitz, Ein Kurs in elementarer Zahlentheorie und Kryptographie, Springer.