Criptanaliza criptosistemului Vigenere

Fie x un cuvant peste {0, 1, . . . , 25} si k ∈ {0, 1, . . . , 25}m o cheie arbitrara,m ≥ 1. Criptarea lui x folosind cheia k va conduce la criptotextul y dat prin

yi = xi + k(((i−1) mod m)+1) mod 26,

pentru orice 1 ≤ i ≤ |x|.Textul obtinut din y extragand simboluri din n ın n pozitii ıncepand cu

pozitia a j-a va fi notat cu yn,j , pentru orice n ≥ 1 si 1 ≤ j ≤ n. Este interesantde remarcat ca, ın cazul ın care y = ek(x), are loc relatia

ym,j = SHIFT (xm,j , kj),

pentru orice 1 ≤ j ≤ m, unde m = |k|.Pentru determinarea cheii k, avand un criptotext y, se va proceda astfel:

1. Determinarea lungimii cheii (m) - folosind testul indexului de coincidenta:

Pentru un text α ∈ {0, 1, . . . , 25}∗, indexul de coincidenta, notat cu IC(α),reprezinta probabilitatea ca un simbol sa apara de cel putin doua ori ınα. Mai exact, IC(α) este dat prin

IC(α) =25∑

i=0

fi(α)|α|

fi(α)− 1|α| − 1

,

unde fi(α) reprezinta numarul de aparitii ale simbolului i ın α.

• Daca α este un text normal ın limba engleza sau un text obtinutdintr-un text normal ın limba engleza extragand simboluri din m ınm pozitii, IC(α) se poate aproxima prin

∑25i=0 p2

i∼= 0.065, unde pi

reprezinta probabilitatea de aparitie a simbolului i;

• Este interesant de remarcat ca criptarea folosind criptosistemul Sh(26)nu modifica acest indicator. Mai exact, IC(SHIFT (α, s)) = IC(α),pentru orice 0 ≤ s ≤ 25.

Astfel, IC(ym,j) = IC(xm,j) ∼= 0.065, pentru m = |k| si orice 1 ≤ j ≤ m.Urmatorul algoritm va conduce la gasirea lungimii cheii:

1

Determina lungimea cheii(y)input: y, un criptotext;output: m, lungimea cheii folosite;begin

m := 0;repeat

m := m + 1;until IC(ym,1) ∼= IC(ym,2) ∼= · · · ∼= IC(ym,m) ∼= 0.065

end.

2. Determinarea efectiva a cheii (k1, . . . , km) - folosind testul indexului decoincidenta mutuala.Pentru α, β ∈ {0, 1, . . . , 25}∗, indexul de coincidenta mutuala, notat cuMIC(α, β), reprezinta probabilitatea ca un simbol sa apara si ın α si ınβ. Mai exact, MIC(α, β) este dat prin

MIC(α, β) =25∑

i=0

fi(α)|α|

fi(β)|β|

.

• Daca α si β sunt texte normale ın limba engleza (sau texte obtinutedin texte normale ın limba engleza extragand simboluri din m ın mpozitii), MIC(α, β) se poate aproxima prin

∑25i=0 p2

i∼= 0.065;

• Daca α este un text normal ın limba engleza (sau un text obtinutdintr-un text normal ın limba engleza extragand simboluri din m ınm pozitii), MIC(α, β) se poate aproxima prin

∑25i=0 pi

fi(β)|β| .

Deoarece xm,j = SHIFT (ym,j ,−kj) si MIC(textnormal, xm,j) ∼= 0.065,pentru orice 1 ≤ j ≤ m, unde m = |k|, putem construi urmatorul algoritmpentru determinarea efectiva a cheii:

Determina cheia(y,m)input: y, un criptotext si m, lungimea cheii;output: k1, . . . , km, componentele cheii folosite;begin

for j:=1 to m dobegin

s := −1;repeat

s := s + 1;until MIC(textnormal, SHIFT (ym,j , s)) ∼= 0.065kj := (26− s) mod 26;

endend.

2