it-swarm-eu.dev

Existuje jednoduchý příklad rutiny asymetrického šifrování / dešifrování?

Velmi dobře rozumím kódům Java, Perl a JavaScript. Zbytek jsem neštudoval, ale myslím, že jsem mohl přijít na to, jak číst/překládat.

Chtěl bych vědět, jaké jsou nejjednodušší asymetrické rutiny. Je to opravdu příliš složité na to, aby se o vás starali?

Jsem opravdu zvědavý, jak je možné mít šifrovací klíč! Jen mi připadá úžasné, že dokáže odolat zpětnému inženýrství, takže chci vědět, jak to funguje!

  1. Je to příliš komplikované.
  2. K čemu je (jedna z) nejjednodušších standardních asymetrických šifrovacích rutin, pro které mohu vyhledat implementaci?
  3. Pokud máte nějaké minimální příklady kódu, které by byly pěkné.

Už jsem zkontroloval odstavce Wikipedie o tom, jak to funguje , ale nedošlo k žádnému matematickému rozdělení ani popisu implementace, jen spousta implementací . Opravdu jsem nechtěl náhodně vybrat, na který z nich se mám podívat, ani jsem nechtěl vzít ten nejběžnější, který očekávám, je nejpevnější a nejsložitější.

Nějaké nápady?

11
Bryan Field

Kredit patří Jeffova odpověď za podrobnosti a Steveova odpověď , což bylo také užitečné. Kredit také směřuje na odpověď tylerl , která obsahovala odkazy na Wikipedii pro všechny funkce, zejména modInverse , také vyjasnila nejasný výchozí bod pro e. Děkuji, Vylepšil jsem vaše odpovědi a pomocí kombinovaných informací ze všech tří odpovědí jsem vytvořil to, co doufám je lepší odpověď.

Klíčem k tomu, aby bylo reverzní inženýrství tak drahé, je použití síly . Druhá odmocnina není tak tvrdá, síla 3 znamená, že potřebujete krychlový kořen, ale síla 34 051 489 je dost těžká. Existují i ​​jiné matematické operace, které je obtížné zpětně analyzovat. Existuje také několik způsobů, jak vytvořit asymetrický algoritmus, ale tato odpověď se zaměřuje na RSA. Nejstarší a nejčastější.

RSA Algoritmus (na základě Java kód )

Níže uvedené výpočty by měly být prováděny s libovolná celá čísla s přesností . (Například BigInt nebo BigInteger)

Generování klíčů:

  • Konstantní délka klíče je l.
  • Obvykle konstantní e_start Může =3 Pro jednoduchost. 0x10001 Je však běžnější, v každém případě je nejlepší číslo nejlepší (z důvodů výkonu generování klíčů a pravděpodobně z jiných důvodů).
  • p a q jsou náhodně generovaná kladná prvočísla, která pro uložení vyžadují až l bitů. (Aby byly tyto pozitivní, bude vždy první bit 0)
  • n = p*q Používá se pro šifrování i dešifrování.
  • e začíná jako e_start. To bude nakonec součástí šifrovacího klíče.
  • m = (p-1)*(q-1) se používá k převodu e na d, který bude použit pro dešifrování.
  • while(gcd(e,m)>1){e+=2} Toto je nezbytné pro další krok.
  • d=modInverse(e,m) Tím se provede standardní aritmická operace. Pravděpodobně nestojí za to prozkoumat mnoho, zvláště pokud to váš programovací jazyk má zabudovaný

Chcete-li šifrovat nebo dešifrovat, nejprve převeďte své bajty na jediné libovolné celé číslo s přesností.

Šifrování: encrypted=(plain^e)%n

Poznámka: Pokud plain>=n, Musíte rozdělit plain na dvě nebo více menších hodnot a zašifrovat je samostatně.

Dešifrování: plain=(encrypted^d)%n

Asymetrické šifrování je obvykle méně účinné než symetrické šifrování. Někdy se asymetrické šifrování používá pouze pro výměnu klíčů.

6
Bryan Field

Pokud jde o RSA, this poskytuje dobrý příklad, který lze sledovat a ukazuje odpovídající příklady vstupu a výstupu. Tato aplikace demo vás provede různými kroky a umožní vám zkontrolovat práci. Někdy stačí kliknout na cestu skrz něco v krocích, jako je to pomůže. U článků na Wikipedii se musíte podívat na aktuální článek o algoritmu: RSA pro matematiku, která odpovídá.

Implementace moudře, můžete to zřetelně spojit v Java v do 30 řádků .

Pro pochopení neexistuje nic jako šifrovací klíč. Spíše existují dva stejné klíče, které mění chod jejich partnerů. Libovolně přiřazujeme jeden z párů jako soukromý a jeden jako veřejný. Věci šifrované jedním klíčem lze dešifrovat druhým klíčem. Toto je princip používaný při podepisování.

Není to problém protisměrného inženýrství, díky kterému jsou klíče bezpečné, ale spíše matematický koncept, že nemůžete rozumně zkontrolovat masivní prostor klíčů (pokud klíč používá opravdu velký počet míst), aby našel odpovídající klíč. Pro faktoringovou práci není reálné urychlení.

Existují i ​​další asymetrické klíčové algoritmy, které byste se měli učit, ale jak se díváte ven, zkusím nejprve pochopit RSA, nejstarší a nejběžnější.

13
Jeff Ferland

Dal jsem dohromady demonstraci RSA pomocí python (python je velmi snadno čitelný, i když jste ho ještě nikdy neviděli). Kód je dostatečně dlouhý, aby se vešel na jeden stránku, ale dostatečně krátkou, abyste ji mohli během několika minut přečíst a porozumět jí.

Protože šifrování/dešifrování lze provést jediným vestavěným příkazem - exp(PLAINTEXT,KEY,MODULUS) -, procházím také celý proces odvozování klíčů.

Kód najdete zde: https://Gist.github.com/1239116

Když spustíte kód, požádá vás o zadání ve tvaru >12345 nebo <12345, Kde > předpona řekne, aby na číslo použil soukromý klíč, zatímco < řekne tomu, aby použil veřejný klíč. V zájmu jednoduchosti kóduje pouze čísla; ale jakmile to máte, kódování libovolných dat je jen otázkou formátování.

6
tylerl

Ve skutečnosti je matematika kolem toho docela jednoduchá, jak tomu rozumím. Vezmete hodnotu do síly nápadně velkého prvočísla (tisíce číslic) a uděláte mod z jiného čísla.

Takže k šifrování máte něco jako: EncryptedBits = (PlainText ^ YourPublicKey)% Modulus

A dešifrovat máte něco jako: PlainText = (EncryptedBits ^ YourPrivateKey)% Modulus

Narazil jsem na docela snadno čitelný dokument zde: http://mathaware.org/mam/06/Kaliski.pdf

Nejsem si však jistý, že se na nějaké knihovny podíváme.

5
Steve

Pokud chcete roztomilé, minimální řešení Perl, existuje klasické řešení od Adama Backa z 1995 :

Bylo vytištěno na tričku, včetně čárového kódu, aby bylo čitelné počítačem, spolu s prohlášením „ Toto tričko je munice “. . Toto prohlášení bylo v USA přesné, než silná kryptografie byla překlasifikována v roce 1996 , aby již nebyla technicky „municí“. Stále však bylo nezákonné vyvážet silnou kryptografii z USA, dokud nebyla nařízení o správě vývozu (EAR) revidována v roce 20 :

Software byl také distribuován jako tetování, e-mailový podpis, poštovní štítek a v mnoha dalších formách, a dokonce se objevil (v rozmazané formě) v New York Times (článek, bez fotografie, je online na Mezi hackerem a těžkým místem ). Novější dvouřádková verze je:

print pack"C*",split/\D+/,`echo "16iII*o\[email protected]{$/=$z;[(pop,pop,unpack"H*",<>
)]}\EsMsKsN0[lN*1lK[d2%Sa2/d0<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<J]dsJxp"|dc`

Všimněte si, že původní přístup se spoléhá na unixový „dc“ program pro libovolnou aritmetickou přesnost aritmetiky. Čistě Perl verze s anotací je na

2
nealmcb