[Powered by Google Translate] [RSA]
[Rob Bowden] [Tommy MacWilliam] [Harvard University]
[Ito ay CS50.] [CS50.TV]
Natin tingnan sa RSA, ang isang malawak na ginamit na algorithm para sa pag-encrypt data.
Encryption algorithm tulad ng Caesar at Vigenère ciphers ay hindi napaka-secure na.
Sa Caesar cipher, ang isang pag-atake ay lamang kailangang subukan ng 25 iba't ibang mga susi
upang makakuha ng plain text ang mensahe.
Habang ang Vigenère cipher ay mas ligtas kaysa sa Caesar cipher
dahil sa ang mas malaking espasyo ng paghahanap para sa key, sa sandaling isang nang-aatake
alam ang haba ng susi sa isang Vigenère cipher,
na maaaring tinutukoy sa pamamagitan ng isang pagtatasa ng mga pattern sa naka-encrypt na teksto,
ang Vigenère cipher ay hindi na mas secure kaysa sa Caesar cipher.
RSA, sa kabilang banda, ay hindi mahina sa pag-atake tulad nito.
Ang Caesar cipher and Vigenère cipher gamitin ang parehong key
sa parehong-encrypt at decrypt ng isang mensahe.
Ang property na ito ay gumagawa ng mga ciphers simetriko key algorithm.
Ang pangunahing problema sa symmetric key algorithm
na umaasa sila sa encrypt at sa pagpapadala ng mensahe
at isa pagtanggap at decrypting ang mensahe
pa sumang-ayon agad sa key sila ay parehong gamitin.
Ngunit kami ay isang bit ng isang startup problema dito.
Paano 2 computer na nais na makipag-ugnay magtatag ng sikretong key sa pagitan ng mga ito?
Kung dapat na lihim ang key, pagkatapos kailangan namin ng isang paraan upang i-encrypt at decrypt ang susi.
Kung ang lahat ng mayroon kaming ay simetriko key cryptography
pagkatapos lamang namin na bumalik sa parehong problema.
RSA, sa kabilang banda, ay gumagamit ng isang pares ng mga susi,
isa para sa encryption at isa pa para sa decryption.
Isa ay tinatawag na ang pampublikong key, at ang iba pa ay ang pribadong key.
Ng public key na ginamit upang i-encrypt ng mga mensahe.
Tulad ng maaaring mong hulaan ng pangalan nito, maaari naming ibahagi ang aming pampublikong key sa
sinuman na gusto namin walang pag-kompromiso sa seguridad ng isang naka-encrypt na mensahe.
Mensahe-encrypt gamit ang isang pampublikong key
maaari lamang decrypted na may kaukulang pribadong key.
Habang maaari mong ibahagi ang iyong mga pampublikong key, dapat mong laging panatilihin ang iyong pribadong key lihim.
at lamang ang pribadong key ay maaaring gamitin upang i-decrypt mensahe
kung ang 2 mga gumagamit ay nais na magpadala ng mga mensahe na naka-encrypt na may RSA
pabalik-balik sa kapwa mga gumagamit ay kailangang magkaroon ng kanilang sariling pampublikong at pribadong key na pares.
Mensahe mula sa user 1 user 2
lamang gamitin ang key user 2 pares, at mga mensahe mula sa user 2 user 1
lamang gamitin ang key pares ng user 1 ng.
Ang katotohanan na may 2 magkahiwalay na mga key upang i-encrypt at i-decrypt mensahe
gumagawa ng RSA ng tabingi key algorithm.
Hindi namin kailangan upang i-encrypt ang pampublikong key upang ipadala ito sa ibang computer
dahil ang susi ay pampublikong pa rin.
Nangangahulugan ito na ang RSA ay hindi ang parehong problema sa startup
bilang simetriko key algorithm.
Kaya kung gusto kong magpadala ng mensahe gamit ang RSA encryption
Rob, ako munang public key ng Rob.
Upang bumuo ng isang pares ng mga susi, Rob ay kailangang pumili ng 2 malaking prime numero.
Ang mga numerong ito ay ginagamit sa parehong pampubliko at pribadong key,
ngunit ang public key ay lamang gumamit ng mga produkto ng mga 2 numero,
hindi ang mga numero mismo.
Kapag ako-encrypt ang mensahe gamit ang pampublikong key ng Rob
Maaari ko bang ipadala ang mensahe sa Rob.
Para sa isang computer, factoring numero ay isang mahirap na problema.
Ng public key, tandaan, ginamit ang produkto ng 2 prime numero.
Ang produktong ito ay dapat magkaroon ng 2 kadahilanan lamang,
kung saan mangyayari ang mga numero na bumubuo sa pribadong key.
Upang i-decrypt ang mensahe, RSA ay gamitin ang pribadong key
o ang mga numero multiply kasama sa proseso ng paglikha ng pampublikong key.
Dahil ito computationally ang mahirap salik ang bilang
ginagamit sa isang pampublikong key sa 2 numero na ginamit sa pribadong key
ito ay mahirap para sa isang pag-atake upang malaman kung ang pribadong key
na kinakailangan upang i-decrypt ang mensahe.
Ngayon ipaalam sa pumunta sa ilang mga mas mababang mga detalye ng antas ng RSA.
Sabihin unang makita kung paano namin maaaring bumuo ng isang pares ng mga susi.
Una, kakailanganin naming ang mga 2 prime numero.
Susubukan naming tawagan mga 2 numero p at q.
Upang makuha p at q, sa kasanayan namin pseudorandomly bumuo ng
malaking numero at pagkatapos ay gamitin ang isang pagsubok para sa pagtukoy kung o hindi
mga numero ay marahil prime.
Maaari naming patuloy na pagbuo ng mga random na numero nang paulit-ulit
hanggang kami ay may 2 primes na maaari naming gamitin.
Dito sabihin pick p = 23 at q = 43.
Tandaan, sa kasanayan, p at q dapat mas malaking numero.
Tulad ng alam namin, ang mas malaki ang mga numero, ang mas mahirap ito ay
upang magpahaginit isang naka-encrypt na mensahe.
Ngunit ito rin mas mahal na-encrypt at decrypt mensahe.
Ngayon madalas na inirerekomenda na p at q ay hindi bababa sa 1024 bits,
kung saan naglalagay ang bawat numero sa mahigit sa 300 decimal digit.
Ngunit makikita namin kukunin ang mga maliit na mga numero para sa halimbawang ito.
Ngayon makikita na namin multiply ang p at q nang magkasama upang makakuha ng isang 3rd numero,
kung saan kami tatawag n.
Sa aming kaso, n = 23 * 43, kung saan = 989.
Namin na n = 989.
Susunod na namin makikita multiply p - 1 may q - 1
upang makakuha ng ika-4 na numero, kung saan kami tatawag m.
Sa aming kaso, m = 22 * ​​42, kung saan = 924.
Mayroon kaming m = 924.
Ngayon, kailangan nating e isang numero na medyo prime sa m
at mas mababa sa m.
Dalawang numero ay relatibong prime o coprime
kung lamang positibong integer na divides sa kanila ng parehong pantay-pantay ay 1.
Sa ibang salita, ang pinakadakilang karaniwang panghati ng e at m
dapat na 1.
Sa pagsasagawa, ito ay karaniwan para sa e prime bilang 65,537
hangga't ang bilang na ito ay hindi mangyayari sa isang kadahilanan ng m.
Para sa aming mga susi, magpapadala kami pumili e = 5
dahil 5 ay relatibong prime sa 924.
Panghuli, kakailanganin naming isa pang numero, kung saan kami tatawag d.
D dapat ilang halaga na natutugunan ang equation de = 1 (mod m).
Mod m Sumisimbolo na ito gagamitin namin ang isang bagay na tinatawag na Modular aritmetika.
Sa Modular aritmetika, sa sandaling ang numero ng ay nakakakuha ng mas mataas kaysa sa ilang itaas bound
ito I-wrap ang pabalik sa paligid sa 0.
Orasan A, halimbawa, gumagamit ng Modular aritmetika.
Isang minuto pagkatapos 1:59, halimbawa, ay 2:00,
hindi 1:60.
Ang kamay ng minuto ay balot sa paligid ng 0
kapag maabot ang isang pang-itaas na nakatali ng 60.
Kaya, maaari naming sabihin 60 ay katumbas ng 0 (mod 60)
at 125 ay katumbas sa 65 ay katumbas sa 5 (mod 60).
Ang aming pampublikong key ay ang pares e at n
kung saan sa kasong ito e ay 5 at n ay 989.
Aming pribadong key ay ang pares d at n,
kung alin sa aming kaso ay 185 at 989.
Pansinin na ang aming mga orihinal na primes p at q hindi lilitaw
kahit saan sa aming mga pribado o pampublikong key.
Ngayon na namin ang aming pares ng key, sabihin kumuha ng isang pagtingin sa kung paano maaari naming i-encrypt ang
at i-decrypt ng mensahe.
Gusto kong magpadala ng mensahe sa Rob,
kaya siya ay upang bumuo ng ang key na ito pares.
Pagkatapos kong tanungin Rob para sa kanyang public key, na makikita ko bang gamitin ang
upang i-encrypt ng isang mensahe upang ipadala sa kanya.
Tandaan, lubos na okay para sa Rob upang ibahagi ang kanyang pampublikong key sa akin.
Ngunit hindi ito ay okay upang ibahagi ang kanyang pribadong key.
Wala akong anumang mga ideya kung ano ang kanyang pribadong key.
Maaari naming masira ang aming mensahe m sa ilang chunks
lahat ng mga mas maliit kaysa sa n at pagkatapos ay i-encrypt ang bawat isa sa mga chunks.
Susubukan naming i-encrypt ang CS50 ang string, na kung saan maaari naming masira up sa 4 chunks,
isa sa bawat titik.
Upang i-encrypt ang aking mensahe, kailangan ko upang i-convert ito sa
ang ilang mga uri ng numeric na representasyon.
Natin pagdugtungin ang mga ASCII na halaga sa ang mga character sa aking mensahe.
Upang i-encrypt ang isang ibinigay na mensahe m
Kailangan ko upang makalkula ang c = m sa e (mod n).
Ngunit m dapat mas maliit kaysa sa n,
kung ang buong mensahe ay hindi maaaring ipinahayag modulo n.
Namin masira m sa ilang mga chunks, lahat ng mga ito ay mas maliit kaysa sa n,
at i-encrypt ang bawat isa sa mga chunks.
Encrypt ang bawat isa sa mga chunks, makuha namin C1 = 67 sa 5 (mod 989)
kung saan = 658.
Para sa aming ikalawang tipak mayroon kaming 83 sa 5 (mod 989)
kung saan = 15.
Para sa aming third tipak mayroon kaming 53 sa 5 (mod 989)
kung saan = 799.
At sa wakas, para sa aming huling tipak mayroon kaming 48 sa 5 (mod 989)
kung saan = 975.
Ngayon ay maaari kaming magpadala sa paglipas ng mga naka-encrypt na halaga sa Rob.
Narito pumunta ka, Rob.
Habang ang aming mensahe sa flight, sabihin tumagal ng isa pang hitsura
sa kung paano namin nakuha na halaga para sa d.
Aming numero d kailangan upang masiyahan ang 5a = 1 (mod 924).
Ginagawa d ang multiplicative kabaligtaran ng 5 modulo 924.
Given 2 integer, at b, pinalawig na Euclidean algorithm
ay maaaring magamit upang mahanap ang pinakadakilang karaniwang panghati ng mga 2 integer.
Mayroon din bigyan kami ng 2 iba pang mga numero, x at y,
na masiyahan ang equation palakol + = ang pinakadakilang karaniwang panghati ng isang at b.
Paano ito makakatulong sa amin?
Well, i-plug sa e = 5 para sa isang
at m = 924 para b
na namin alam na ang mga bilang na ito ay coprime.
Kanilang mga pinakadakilang karaniwang panghati ay 1.
Ito ay nagbibigay sa amin 5x + 924y = 1
o 5x = 1 - 924y.
Ngunit kung lamang namin pakialam tungkol sa lahat ng modulo 924
pagkatapos ay maaari naming ilagay ang - 924y.
Isipin pabalik sa orasan.
Kung ang kamay ng minuto sa 1 at ang eksaktong 10 oras pumasa,
alam namin ang kamay ng minuto ay pa rin sa 1.
Narito namin magsimula sa 1 at pagkatapos ay I-wrap sa paligid eksaktong y beses,
kaya pa rin namin sa 1.
Mayroon kaming 5x = 1 (mod 924).
At dito x na ito ay ang parehong bilang d na namin ang hinahanap para sa bago,
kaya kung ginagamit namin ang pinalawig na Euclidean algorithm
upang makuha ang numero ng x, na ang bilang dapat naming gamitin ang aming d.
Ngayon sabihin magpatakbo ng pinalawig na Euclidean algorithm para sa isang = 5
at b = 924.
Gagamitin namin ang isang pamamaraan na tinatawag talahanayan ng paraan ng.
Aming talahanayan ay 4 haligi, x, y, d, at k.
Aming talahanayan nagsisimula off na may 2 mga hilera.
Sa unang hilera ay may kami ng 1, 0, pagkatapos ay ang aming halaga ng isang, na kung saan ay 5,
at ang aming pangalawang hilera ay 0, 1, at ang aming halaga para sa b, na 924.
Ang halaga ng ika-4 na haligi, k, ay ang resulta
ng paghahati ang halaga ng d sa hilera itaas nito na may halaga ng d
sa parehong hilera.
Mayroon kaming 5 na hinati sa pamamagitan ng 924 ay 0 na may ilang natitira.
Iyon ay nangangahulugang mayroon kaming k = 0.
Ngayon ang halaga ng bawat iba pang mga cell ay ang halaga ng cell 2 mga hilera sa itaas nito
minus ang halaga ng hilera itaas nito beses k.
Natin magsimula sa d sa 3rd hilera.
Mayroon kaming 5-924 * 0 = 5.
Susunod na kami ay may 0 - 1 * 0 na 0
at 1 - 0 * 0 na 1.
Hindi masyadong masamang, kaya sabihin ilipat sa sa susunod na hilera.
Una kailangan namin ang aming halaga ng k.
924 na hinati sa pamamagitan ng 5 = 184 na may ilang natitira,
kaya ang aming halaga para sa k ay 184.
Ngayon 924 - 5 * 184 = 4.
1 - 0 * 184 1 at 0 - 1 * 184 ay -184.
Lahat ng karapatan, sabihin sa susunod na hilera.
Ang aming halaga ng k ay 1 dahil
5 na hinati sa pamamagitan ng 4 = 1 may ilang natitira.
Punan natin sa iba pang mga hanay.
5 - 4 * 1 = 1.
0 - 1 * 1 = -1.
At 1-184 * 1 ay 185.
Natin makita kung ano ang aming susunod na halaga ng k ay.
Well, mukhang mayroon kaming 4 na hinati sa pamamagitan ng 1, na kung saan ay 4.
Sa kasong ito na kung saan kami ay paghahati ng 1 tulad k na katumbas ng
ang halaga ng d sa itaas hilera ay nangangahulugan na tapos na kami sa aming algorithm.
Maaari naming makita dito mayroon kaming x = 185 at y = -1 sa huling hilera.
Natin ngayon bumalik sa aming orihinal na layunin.
Sinabi namin na ang halaga ng x bilang resulta ng patakbuhin ito algorithm
ay ang multiplicative kabaligtaran ng isang (mod b).
Iyon ay nangangahulugan na ang 185 ang multiplicative kabaligtaran ng 5 (mod 924)
na nangangahulugan na kami ay may isang halaga ng 185 para d.
Ang katotohanan na ang d = 1 sa huling hilera
verify e na coprime sa m.
Kung ito ay hindi 1 pagkatapos ay namin upang pumili ng isang bagong e.
Ngayon ipaalam sa makita kung Rob ay natanggap ang aking mensahe.
Kapag may nagpadala sa akin ng isang naka-encrypt na mensahe
hangga't ko ang iningatan ang aking pribadong key lihim ng
Ako ang isa lamang na maaari i-decrypt ang mensahe.
Upang i-decrypt isang tipak c ko makalkula ang orihinal na mensahe
ay katumbas sa tipak sa d kapangyarihan (mod n).
Tandaan na d at n mula sa aking pribadong key.
Upang makakuha ng buong mensahe mula sa chunks namin i-decrypt ang bawat tipak
at pagdugtungin ang mga resulta.
Eksakto kung paano ka tiwasay ang RSA?
Ang katotohanan ay, hindi namin alam.
Security ay batay sa kung gaano katagal ito ay magdudulot ng isang nang-aatake sa magpahaginit ng mensahe
-encrypt na may RSA.
Tandaan na ang isang pag-atake ay may access sa iyong mga pampublikong key,
na naglalaman ng parehong e at n.
Kung ang umaatake ang namamahala sa salik n sa nito 2 primes, p at q,
maaaring siya kalkulahin d gamit ang pinalawig na Euclidean algorithm.
Ito ay nagbibigay sa kanya ang pribadong key, na maaaring magamit upang i-decrypt ang mensahe anumang.
Ngunit kung gaano kabilis namin salik ng mga integer?
Muli, hindi namin alam.
Walang natagpuan ang isang mabilis na paraan ng paggawa nito,
na nangangahulugan na ang naibigay na malaki sapat n
tumagal ang isang attacker unrealistically mahaba
salik ang bilang.
Kung may isang taong nagsiwalat isang mabilis na paraan ng integer factoring
RSA ay nasira.
Ngunit kahit na integer paktorisasyon ay likas na mabagal
ang RSA algorithm ay maaaring pa rin magkaroon ng ilang mga depekto sa
na nagbibigay-daan para sa madaling decryption ng mga mensahe.
Walang sinuman ay natagpuan at ipinahayag tulad kapintasan,
ngunit na ay hindi nangangahulugan na hindi isa ay umiiral.
Sa teorya, ang isang tao ay maaaring ang doon pagbabasa ng lahat ng data na na-encrypt na may RSA.
May isa pang bit ng isang isyu sa privacy.
Kung Tommy ine-encrypt ng ilang mensahe gamit ang aking pampublikong key
at isang pag-atake ine-encrypt ng ang parehong mensahe na gamit ang aking pampublikong key
umaatake ay makita na ang 2 mensahe ay magkapareho
at sa gayon ay malaman kung ano Tommy-encrypt.
Upang maiwasan ito, ang mga mensahe ay karaniwang may palaman sa random bits
bago ine-encrypt sa gayon ay ang parehong mensahe na-encrypt
nang maraming beses ang magiging hitsura ng iba't ibang hangga't ang padding sa mensahe ay naiiba.
Ngunit tandaan kung paano mayroon kaming upang hatiin ang mga mensahe sa mga chunks
sa gayon na ang bawat tipak ay mas maliit kaysa sa n?
Padding ang chunks ay nangangahulugan na maaari naming upang hatiin ang mga bagay up
sa higit pang mga chunks dahil may palaman tipak ay dapat na mas maliit kaysa sa n.
Encryption at decryption medyo mahal sa RSA,
at sa gayon ay nangangailangan masira ng mensahe sa maraming mga chunks ay maaaring masyadong mahal.
Kung ang isang malaking dami ng data kailangang naka-encrypt at decrypted
maaari naming pagsamahin ang mga benepisyo ng simetriko key algorithm
sa mga RSA upang makakuha ng parehong seguridad at kahusayan.
Bagaman hindi namin ay pumunta sa dito,
AES ay symmetric key algorithm tulad ng Vigenère at Caesar ciphers
ngunit mas mahirap sa magpahaginit.
Siyempre, hindi namin maaaring gamitin ang AES walang pagtaguyod ng isang nakabahaging sikretong key
sa pagitan ng 2 system, at nakita namin ang problema sa na bago.
Ngunit ngayon na maaari naming gamitin RSA magtatag sa nakabahaging sikretong key sa pagitan ng 2 system.
Susubukan naming tawagan ang computer sa pagpapadala ng data sa nagpadala
at computer pagtanggap ng data ang receiver.
Receiver ay isang RSA key pares at ipapadala
ang pampublikong key sa nagpadala.
Ang nagpadala ay bumubuo ng isang AES key,
ine-encrypt ito sa RSA public key ang receiver,
at ipapadala ang AES key sa receiver.
Receiver ang decrypts ang mensahe na may RSA pribadong key.
Parehong sa nagpadala at ang receiver ngayon ay may isang shared key AES sa pagitan ng mga ito.
AES, na mas mabilis sa encryption at decryption kaysa RSA,
ay maaari na ngayong gamitin upang i-encrypt ang malaking volume ng data at ipadala ang mga ito sa receiver,
na maaaring i-decrypt gamit ang parehong key.
AES, na mas mabilis sa encryption at decryption kaysa RSA,
ay maaari na ngayong gamitin upang i-encrypt ang malaking volume ng data at ipadala ang mga ito sa receiver,
na maaaring i-decrypt gamit ang parehong key.
Kailangan lang namin RSA upang ilipat ang ibinahagi key.
Hindi na namin kailangang gumamit ng RSA sa lahat.
Mukhang Mayroon akong isang mensahe.
Hindi mahalaga kung sinuman basahin kung ano ang sa eroplano papel bago nahuli ko ito
dahil ako ang isa lamang na ang pribadong key.
Natin i-decrypt ang bawat isa ng ang mga chunks sa mensahe.
Ang unang tigkal, 658, itataas namin sa d kapangyarihan, na kung saan ay 185,
mod n, kung saan ay 989, ay katumbas ng 67,
na ang sulat C sa ASCII.
Ngayon, papunta sa pangalawang tipak.
Ang pangalawang tipak ay halaga 15,
na aming itataas sa 185 kapangyarihan,
mod 989, at ito ay katumbas ng 83
na ang letrang S sa ASCII.
Ngayon para sa ikatlong tigkal, na may halaga 799, itataas namin sa 185,
mod 989, at ito ay katumbas ng 53,
na ang halaga ng character 5 sa ASCII.
Ngayon para sa huling tipak, na may halaga 975,
itataas namin sa 185, mod 989,
at ito ay katumbas ng 48, na kung saan ay ang halaga ng character 0 sa ASCII.
Ang pangalan ko ay Rob Bowden, at ito ay CS50.
[CS50.TV]
RSA sa lahat.
RSA sa lahat. [Tawa]
Sa lahat.