11. előadás

Titkosítás

• Szimmetrikus-aszimmetrikus titkosítás

• Kódtáblák: szöveges ábrázolás

• Módosított, speciális kódtábla: titkosítás

Szimmetrikus titkosítás

• Ugyanazt a kucslot használja titkosításhoz és visszafejtéshez is
• Ma általában: kulcs alapján valamilyen matematikai módszert használva
  • Legegyszerűbb: XOR

Aszimmetrikus titkosítás

• Különböző kulcs a titkosításra és a visszafejtésre
• Gyakran használják kézfogásra

Maradékosztályok

Alapja az oszthatóság => maradékosztályok (egymással kongruens számok halmaza)

Kongruencia (kongruens):

• Ha az \(\(m\)\) (\(\(\neq 0\)\)) osztja az \(\(a-b\)\) különbséget, akkor azt mondjuk, hogy az \(\(a\)\) szám kongruens \(\(b\)\)-vel modulo \(\(m\)\) ( → ugyan abban a maradékosztályban vannak mod m )
• (Két szám kongruens, ha m-mel osztva ugyanazt a maradékot adják)
• Jelölés: \(a \equiv b \mod m\)

Kongruencia -- Mateking

Kongruencia tulajdonságai:

Számrend: 13. diasor (RSA): valahol a 9. dia környékén

Maradékrendszer: \(\(x_1; x_2; ... x_m\)\) teljes maradékrendszer \(\(mod \ m\)\), ha tetszőleges \(\(y\)\) egész számhoz pontosan egy olyan \(\(x_j\)\) található, amelyre \(\(y \equiv x_j \mod m\)\)

Euler-féle \(\varphi\) függvény

\(\(\varphi(m)\)\) az \(\(m\)\)-nél nem nagyobb, \(\(m\)\)-hez relatív prím pozitív egészek száma

Ha \(\(p_1\)\) és \(\(p_2\)\) prímek, akkor \(\(\varphi(p_1*p_2) = (p_1-1)(p_2-1)\)\)

Euler tétele:

Ha \(\((a;m)=1\)\), akkor \(\(a^{\varphi(m)} \equiv 1 \mod m\)\)

Ebből, Fermat tétele:

Ha \(\(p\)\) prím és \(\((a;p)=1\)\)

• \(\Rightarrow a^{p-1} \equiv 1 \mod p\)

• \(\Rightarrow a^{p} \equiv a \mod p\)

RSA algoritmus

Leggyakoribb asszimetrikus titkosítási algoritmus