[Powered by Google Translate] [RSA]
[Rob Bowden] [Tommy MacWilliam] [Harvard University]
[To je CS50.] [CS50.TV]
Pojďme se podívat na RSA, široce používaný algoritmus pro šifrování dat.
Šifrovací algoritmy jako Caesar a Vigenère kódy nejsou příliš bezpečné.
S Caesara, útočník potřebuje pouze vyzkoušet 25 různých klíčů
dostat zprávu na prostý text.
Zatímco Vigenère kód je bezpečnější než Caesara
vzhledem k větší hledání prostor pro klíče, jednou útočník
ví, délku klíče v Vigenère kód,
, které mohou být stanovena prostřednictvím analýzy vzorků v šifrovaných textu,
Vigenère kód není to, že mnohem bezpečnější než Caesara.
RSA, na druhé straně, není náchylné k útokům, jako je tento.
Caesarova šifra a Vigenère kód používat stejný klíč
jak šifrovat a dešifrovat zprávy.
Tato vlastnost dělá Tyto šifry symetrické klíčových algoritmů.
Základním problémem symmetric klíčové algoritmy
je to, že oni se spoléhají na jedné straně a šifrování a odeslání zprávy
a jeden přijímající a dešifrování zprávy
se již dohodli předem na klíč budou oba používat.
Ale máme trochu problém při spuštění zde.
Jak 2 počítače, které chtějí komunikovat vytvořit tajný klíč mezi nimi?
Pokud klíč musí být tajná, pak potřebujeme způsob, jak šifrovat a dešifrovat klíč.
Pokud vše, co máme, je symetrický klíč kryptografie
pak jsme právě přišli zpět do stejného problému.
RSA, na druhé straně, používá dvojice klíčů,
jeden pro šifrování a jiný pro dešifrování.
Jedním z nich je tzv. veřejný klíč, a druhý je soukromý klíč.
Veřejný klíč je použit k zašifrování zprávy.
Jak asi tušíte podle názvu, můžeme podělit o naše veřejný klíč s
někdo chceme, aniž by byla ohrožena bezpečnost šifrované zprávě.
Zprávy šifrována pomocí veřejného klíče
lze dešifrovat pouze s odpovídajícím privátním klíčem.
I když můžete sdílet váš veřejný klíč, měli byste mít svůj soukromý klíč v tajnosti.
a to pouze soukromý klíč může být použit k dešifrování zpráv
pokud 2 uživatelé chtějí poslat zprávy šifrované pomocí RSA
tam a zpět oba uživatelé musí mít svou vlastní veřejné a soukromé klíče.
Zprávy od uživatele 1 až 2 uživateli
používat pouze uživatelské 2 klíčovou pár, a zprávy od uživatele 2 k uživateli 1
používat pouze uživatelské 1 klíčovou dvojici.
Skutečnost, že jsou 2 samostatné klíče k šifrování a dešifrování zpráv
dělá RSA asymetrický klíčový algoritmus.
Nepotřebujeme k zašifrování veřejný klíč, aby se odeslat ji do jiného počítače
, protože klíč je veřejný stejně.
To znamená, že RSA nemá stejný spouštěcí problém
jako symmetric klíčové algoritmy.
Takže když chci odeslat zprávu pomocí RSA šifrování
Robymu, budu muset nejprve Rob veřejný klíč.
Chcete-li generovat dvojici klíčů, Rob musí vybrat 2 velká prvočísla.
Tato čísla budou použita v obou veřejných a soukromých klíčů,
ale veřejný klíč bude používat pouze produkt těchto 2 čísel,
ne samotná čísla.
Poté, co jsem šifrována zprávu pomocí Rob veřejný klíč
Mohu poslat zprávu Rob.
U počítače, factoring čísla je obtížný problém.
Veřejný klíč, pamatujte, používal produkt 2 prvočísel.
Tento výrobek pak musí mít pouze 2 faktory,
které se dějí, že jsou čísla, která tvoří soukromý klíč.
Aby bylo možné dešifrovat zprávy, bude RSA použijte tento soukromý klíč
nebo čísla násobí společně v procesu vytváření veřejného klíče.
Vzhledem k tomu, že je výpočetně těžké faktoru se počet
používá ve veřejném klíči do 2 čísla používaných v privátním klíčem
je to těžké pro útočníkovi zjistit soukromého klíče
že bude nutné dešifrovat zprávy.
Teď pojďme do některých nižších úrovní detailů RSA.
Podívejme se nejprve, jak můžeme vytvořit dvojici klíčů.
Za prvé, budeme potřebovat 2 prvočísla.
Zavoláme tyto 2 čísla p a q.
Při výběru p a q, v praxi bychom pseudorandomly vytvářet
velké množství a pak použít test pro určení, zda
tato čísla jsou pravděpodobně připravit.
Můžeme si ponechat generování náhodných čísel znovu a znovu
až budeme mít 2 prvočísla, které můžeme použít.
Zde pojďme vybrat p = 23 a q = 43.
Pamatujte si, že v praxi by p a q být mnohem větší čísla.
Pokud je nám známo, že čím větší čísla, tím je těžší
bezva zašifrovanou zprávu.
Ale je to také dražší pro šifrování a dešifrování zpráv.
Dnes se často doporučuje, aby p a q jsou alespoň 1024 bitů,
která staví na každé číslo na více než 300 desetinných míst.
Ale budeme vybírat tyto malé čísla pro tento příklad.
Teď budeme násobit p a q společně získat třetí číslo,
které budeme nazývat n.
V našem případě, n = 23 * 43, který = 989.
Jsme N = 989.
Další budeme násobit p - 1 s q - 1
získat čtvrté číslo, které budeme nazývat m.
V našem případě, m = 22 * ​​42, který = 924.
Máme m = 924.
Teď budeme potřebovat číslo e, která je nesoudělná m
a méně než m..
Dvě čísla jsou nesoudělná, nebo coprime
pokud jen pozitivní celé číslo, které dělí obě rovnoměrně je 1.
Jinými slovy, největší společný dělitel E a M
musí být 1.
V praxi, to je společné pro e být prvočíslo 65537
tak dlouho, jak je toto číslo se nestane být faktor m..
Pro naše klíče, budeme vybírat e = 5
od 5 je nesoudělná 924.
Nakonec, budeme potřebovat jeden větší počet, který budeme nazývat d.
D musí být nějaká hodnota, která splňuje rovnici de = 1 (mod m).
To m mod znamená budeme používat něco, co nazývá modulární aritmetika.
V modulární aritmetice, jednou číslo dostane vyšší než některé horní mez
to se zalomí zpět k 0.
Hodiny, například, používá modulární aritmetiku.
Minutu po 01:59, například, je 2:00,
ne 1:60.
Minutová ručička se omotal kolem 0
po dosažení horní hranice 60.
Takže můžeme říci, 60 je ekvivalentní 0 (mod 60)
a 125 je ekvivalent k 65 je ekvivalentní 5 (mod 60).
Naše veřejné klíč bude dvojice e a n
kde v tomto případě je e 5 a n je 989.
Naše vlastní klíč bude dvojice d a n,
která je v našem případě 185 a 989.
Všimněte si, že náš původní prvočísla p a q se nezobrazí
kdekoli v našich soukromých nebo veřejných klíčů.
Nyní, když máme pár klíčů, pojďme se podívat na to, jak můžeme zašifrovat
a dešifrovat zprávy.
Chci poslat zprávu Rob,
tak on bude tím, kdo k vygenerování této dvojice klíčů.
Zeptám se Rob jeho veřejného klíče, který budu používat
k zašifrování zprávy poslat k němu.
Pamatujte si, že je to naprosto v pořádku Rob sdílet jeho veřejný klíč se mnou.
Ale to by nebylo v pořádku sdílet svůj soukromý klíč.
Nemám ponětí, co jeho soukromý klíč je.
Můžeme porušit zprávu m do několika kousky
všechny menší než n a potom zašifrovat každý z těchto bloků.
Budeme-li zašifrovat řetězec CS50, které můžeme rozdělit do 4 kusy,
jeden na písmeno.
Za účelem šifrování můj vzkaz, budu muset převést do
nějaký druh numerické reprezentace.
Pojďme zřetězit hodnoty ASCII s postavami v mé zprávě.
Aby bylo možné šifrování danou zprávu m
Budu se muset počítat c = m na e (mod n).
Ale m musí být menší než n,
jinak celá zpráva nemůže být vyjádřena modulo n.
Můžeme rozdělit m až do několika bloků, z nichž všechny jsou menší než n,
a šifrovat každý z těchto bloků.
Šifrování každý z těchto bloků, dostaneme c1 = 67 k 5 (mod 989)
které = 658.
Pro našeho druhého bloku máme 83 na 5 (mod 989)
které = 15.
Pro našeho třetího bloku máme 53 na 5 (mod 989)
které = 799.
A konečně, pro náš poslední kus máme 48 na 5 (mod 989)
který = 975.
Nyní můžeme poslat přes tyto šifrované hodnoty Rob.
Tady to máš, Robe.
Zatímco naše poselství je v letu, pojďme se ještě jednou podívat
na to, jak jsme se dostali, že hodnotu d.
Naše číslo d potřebné k uspokojení 5d = 1 (mod 924).
To je d multiplikativní inverzní 5 modulo 924.
Vzhledem k tomu, 2 celá čísla a, b, rozšířená Euclidean algoritmus
může být použit k nalezení největšího společného dělitele těchto 2 čísel.
To bude také dát nám další 2 čísla, x a y,
které splňují rovnici ax + by = největší společný dělitel a a b.
Jak to pomůže nám?
No, zasunutím e = 5 pro
a m = 924 pro b
již víme, že tato čísla jsou coprime.
Jejich největší společný dělitel je 1.
To nám dává 5x + 924y = 1
nebo 5x = 1 - 924y.
Ale pokud nás však zajímá pouze o všem modulo 924
pak můžeme přetáhnout - 924y.
Vzpomeňte si na hodiny.
Pokud minutová ručička je na 1 a pak přesně 10 hodin projít,
víme, že minutová ručička bude stále na 1.
Zde začínáme na 1 a pak zabalit kolem přesně y časy,
takže budeme stále v 1.
Máme 5x = 1 (mod 924).
A tady to x je stejný jako v d jsme hledali dříve,
takže pokud budeme používat rozšířené Euclidean algoritmus
a stáhni číslo x, že je to číslo bychom měli používat jako náš d..
Nyní pojďme spustit rozšířený euklidovský algoritmus pro = 5
a b = 924.
Použijeme metodu nazvanou tabulka metoda.
Naše tabulka bude mít 4 sloupce, x, y, d, a k.
Náš stůl začíná s 2 řádky.
V první řadě máme 1, 0, pak se naše hodnota, která je 5,
a naše druhá řada je 0, 1, a naše hodnota pro B, který je 924.
Hodnota 4. sloupce, k, bude výsledek
dělení hodnotu d na řádku nad ním s hodnotou d
na stejném řádku.
Máme 5 děleno 924 je 0 s nějakým zbytkem.
To znamená, že máme k = 0.
Nyní se hodnota každého jiného buňky bude hodnota z buněk 2 řadách nad ní
minus hodnota na řádku nad ním časy k..
Pojďme začít s d v 3. řadě.
Máme 5-924 * 0 = 5.
Pak máme 0-1 * 0, což je 0
a 1 - 0 * 0, která je 1.
Není to tak zlé, takže se pojďme přesunout na další řádek.
Nejprve musíme naši hodnotu k..
924 děleno 5 = 184 s nějakým zbytkem,
takže naše hodnota k je 184.
Nyní 924-5 * 184 = 4.
1-0 * 184 je 1 a 0 - 1 * 184 je -184.
Dobře, pojďme udělat další řádek.
Naše hodnota k bude 1, protože
5 děleno 4 = 1 s nějakým zbytkem.
Pojďme vyplnit v ostatních sloupcích.
5-4 * 1 = 1.
0-1 * 1 = -1.
A 1 - 184 * 1 je 185.
Podívejme se, co naše další hodnota součinitele bude.
No, vypadá to, že máme 4 děleno 1, což je 4.
V tomto případě, kdy jsme vydělením 1 tak, že k je rovna
hodnota d ve výše uvedeném řádku znamená, že skončíme s naším algoritmem.
Můžeme vidět, že máme x = 185, y = -1 v posledním řádku.
Pojďme se nyní vrátit k našemu původnímu cíli.
Řekli jsme, že hodnota x v důsledku provozu tohoto algoritmu
by multiplikativní inverzní k (mod b).
To znamená, že 185 je multiplikativní inverzní 5 (mod 924)
, což znamená, že se mají hodnotu 185 pro d.
Skutečnost, že d = 1 v posledním řádku
ověří, že e byla coprime k m..
Pokud by tomu tak nebylo 1, pak budeme muset vybrat nového e.
Nyní se podíváme, jestli Rob získal mou zprávu.
Když mi někdo pošle šifrovanou zprávu
tak dlouho, jak jsem držel jsem soukromý klíč v tajnosti
Jsem jediný, kdo může dešifrovat zprávu.
Chcete-li dešifrovat kus c mohu vypočítat původní zprávu
je rovna bloku až d moci (mod n).
Pamatujte si, že d a n jsou z mého soukromého klíče.
Chcete-li získat kompletní zprávu z jeho kousky jsme dešifrovat každý blok
a zřetězit výsledky.
Přesně tak, jak bezpečný je RSA?
Pravdou je, že nevíme.
Bezpečnost je založena na tom, jak dlouho to bude trvat, aby útočník bezva zprávu
šifrován pomocí RSA.
Pamatujte si, že útočník má přístup k vašemu veřejný klíč,
který obsahuje jak e a n.
Pokud útočník dokáže faktor N do svých 2 připraví, p a q,
pak by mohla vypočítat d pomocí rozšířeného Euclidean algoritmus.
To jí dává soukromý klíč, který může být použit k dešifrování žádné zprávy.
Ale jak rychle můžeme vytknout celá čísla?
Opět, nevíme.
Nikdo našel rychlý způsob, jak to udělat,
To znamená, že vzhledem k dostatečně velká n
to by se útočníkovi nereálně dlouho
započítávat číslo.
Pokud někdo odhalil rychlý způsob factoringových celých čísel
RSA by být rozbit.
Ale i když faktorizace celého čísla je ve své podstatě pomalé
RSA algoritmus mohl ještě mít nějakou vadu v tom
, která umožňuje snadné dešifrování zpráv.
Nikdo našel a odhalil tak chybu ještě,
ale to neznamená že neexistuje.
Teoreticky by mohl někdo být venku čtení všech dat zašifrovány pomocí RSA.
Je tu další kousek o ochraně osobních vydání.
Pokud Tommy zašifruje nějakou zprávu pomocí veřejného klíče svůj
a útočník zašifruje stejný zprávu pomocí veřejného klíče svůj
útočník uvidí, že 2 zprávy jsou totožné
a tak vím, co Tommy šifrovány.
Aby se tomu zabránilo, jsou zprávy obvykle čalouněny s náhodnými bity
před zašifrován tak, že stejná zpráva zašifrována
vícekrát bude vypadat jinak, pokud polstrování na zprávy se liší.
Ale nezapomeňte, jak máme rozdělit zpráv na kousky
tak, že každý blok je menší než n?
Čalounění na kusy znamená, že možná budeme muset rozdělit věci do
do ještě větší kousky od polstrovaný bloku musí být menší než n..
Šifrování a dešifrování jsou poměrně drahé s RSA,
a tak museli rozbít zprávu do mnoha kousky může být velmi nákladné.
Pokud velký objem dat musí být šifrována a dešifrována
můžeme spojit výhody symmetric klíčové algoritmy
s těmi RSA dostat i bezpečnost a efektivitu.
I když nepůjdeme do toho tady,
AES je symetrický algoritmus klíče jako Vigenère a Caesar šifry
ale mnohem těžší prasknout.
Samozřejmě, nemůžeme použít AES bez stanovení sdíleného tajného klíče
mezi 2 systémy, a my jsme viděli problém s tím předtím.
Ale teď můžeme použít RSA založit sdíleného tajného klíče mezi 2 systémy.
Zavoláme počítač odesílání dat odesílatele
a počítač přijímající údaje přijímače.
Přijímač má pár RSA klíčů a odešle
veřejný klíč odesílatele.
Odesílatel generuje klíč AES,
zašifruje s přijímačem RSA veřejného klíče,
a odešle klíč AES k přijímači.
Přijímač dešifruje zprávu s RSA privátním klíčem.
Odesílatel i příjemce mají nyní společný klíče AES mezi nimi.
AES, což je mnohem rychlejší při šifrování a dešifrování, než RSA,
lze nyní použít pro šifrování velkých objemů dat a poslat je do přijímače,
kdo může dešifrovat pomocí stejného klíče.
AES, což je mnohem rychlejší při šifrování a dešifrování, než RSA,
lze nyní použít pro šifrování velkých objemů dat a poslat je do přijímače,
kdo může dešifrovat pomocí stejného klíče.
Jsme jen potřebovali RSA přenést sdílený klíč.
Už nepotřebujeme používat RSA vůbec.
Vypadá to, že jsem dostal zprávu.
Nezáleží na tom, jestli někdo přečíst, co je na papírové letadlo předtím, než jsem ho chytil
protože jsem jediný, kdo má soukromý klíč.
Pojďme dešifrovat každý z bloků ve zprávě.
První blok, 658, jsme zvýšit na d síle, která je 185,
mod n, které je 989, je rovna 67,
který je písmeno C v ASCII.
Nyní, na druhé bloku.
Druhý blok má hodnotu 15,
které jsme zvýšit na 185. moci,
mod 989, a to se rovná 83
který je písmeno S v ASCII.
Nyní za třetí bloku, který má hodnotu 799, zvýšíme na 185,
mod 989, a to se rovná 53,
což je hodnota znaku 5 v ASCII.
Nyní pro poslední kus, který má hodnotu 975,
chováme na 185, mod 989,
a to se rovná 48, což je hodnota znaku 0 v ASCII.
Mé jméno je Rob Bowden, a to je CS50.
[CS50.TV]
RSA vůbec.
RSA vůbec. [Smích]
Na všech.