Topic, w13: Public-key cryptography
Per Andersson
Denna vecka tittar vi alltså på artikeln
http://en.wikipedia.org/wiki/Public-key_cryptography
Vi utgår från denna artikeln och ser var vi hamnar.
Jag tänker mig att vi bara svarar i den här tråden när vi läst.
Skriv ner tankar och reflektioner så får vi igång diskussioner.
-- Per
Per Andersson
Vad innebär det att ett nyckelpar (publik-privat) är matematisk relaterade?
-- Per
Sebastian Jansson
Det måste väl ha att göra med att ena nyckeln är deriverbar ur den andra.
Det är ju teoretiskt möjligt att fiska fram den privata nyckeln ur den publika men det kostar oftast mycket kraft och tar en miljon år eller så.
Vänliga hälsningar,
Sebastian
-- Per
To unsubscribe from this group, send email to distributed-studies+unsubscribegooglegroups.com or reply to this email with the words "REMOVE ME" as the subject.
Sebastian Jansson
>Vad innebär det att ett nyckelpar (publik-privat) är matematisk relaterade?
Det är ju teoretiskt möjligt att fiska fram den privata nyckeln ur den publika men det kostar oftast mycket kraft och tar en miljon år eller så.
Vänliga hälsningar,
Sebastian
-- Per
Olof Kamp
>
> >Vad innebär det att ett nyckelpar (publik-privat) är matematisk relaterade?
>
> Det måste väl ha att göra med att ena nyckeln är deriverbar ur den andra.
> Det är ju teoretiskt möjligt att fiska fram den privata nyckeln ur den
> publika men det kostar oftast mycket kraft och tar en miljon år eller så.
>
Stämmer. Ett exempel (enkel förklaring av RSA):
Man väljer två stora primtal, p och q. Man multiplicerar dem och får
ett nytt
tal, N. Sen väljer man ett tal e som kommer användas till kryptering
och
beräknar (hur? detaljer...) talet d som kommer användas till
dekryptering.
N tillsammans med e utgör den publika nyckeln, och N tillsammans med d
utgör den privata.
För att kryptera ett meddelande, m, så tar man m^e mod N. och för att
dekryptera det krypterade meddelandet, c, tar man c^d mod N. Det blir
så
här eftersom man räknade ut d baserat på e och N så att d och e blev
"varandras invers i N" (m^(e*d) = m mod N).
Den här algoritmen är säker för att man behöver p och q för att
beräkna d.
Tyvärr (?) finns det ingen tillräckligt snabb algoritm för att beräkna
primtalsfaktorer. Utan primtalsfaktorerna har man ett så kallat
"discrete log
problem" och det finns ingen känd snabb lösning till det.
Sen finns det säkert andra sätt att ta fram nycklar på, men det kan ju
vara
skönt med ett exempel. Hoppas det inte blev för rörigt.
Per Andersson
>>Vad innebär det att ett nyckelpar (publik-privat) är matematisk relaterade?
>
> Det måste väl ha att göra med att ena nyckeln är deriverbar ur den andra.
> Det är ju teoretiskt möjligt att fiska fram den privata nyckeln ur den
> publika men det kostar oftast mycket kraft och tar en miljon år eller så.
Det är väl själva grejen med public-key cryptography att du med endast den ena
nyckeln inte kan beräkna den andra. Du kan ju däremot göra en brute-force
nyckelsökningsattack och på så sätt hitta den privata nyckeln.
-- Per
Sebastian Jansson
Hur lång tid och kraft det tar är väl en helt annan femma.
Vänliga hälsningar,
Sebastian
To unsubscribe from this group, send email to anarthesis+unsubscribegooglegroups.com or reply to this email with the words "REMOVE ME" as the subject.
Per Andersson
> Men om någonting är matematiskt relaterad med någonting annat måste det väl
> ändå innebära att man alltid kan beräkna den andra?
> Hur lång tid och kraft det tar är väl en helt annan femma.
Jo, men att brute-forca fram den ena ur den andra är ju ingen
matematisk relation.
-- Per
Sebastian Jansson
>> ändå innebära att man alltid kan beräkna den andra?
>> Hur lång tid och kraft det tar är väl en helt annan femma.
>
>matematisk relation.
Grulof Kamp nämnde ju att det inte finns några effektiva algoritmer:
>Tyvärr (?) finns det ingen tillräckligt snabb algoritm för att beräkna primtalsfaktorer. Utan primtalsfaktorerna har man ett så kallat "discrete log problem" och det finns ingen känd snabb lösning till det.
LIOL
Vänliga hälsningar,
Sebastian
Axel Lyckberg
-- Per
To unsubscribe from this group, send email to anarthesis+unsubscribegooglegroups.com or reply to this email with the words "REMOVE ME" as the subject.
Men det finns väl en matematisk relation, primtalsfaktorisering. Men den går inte att lösa i polynomiell(?) tid i förhållande till inputet. Om man inte har en sån där datamaskin som alla forskar på, som vissa säger att NSA har (fet chans). Men det finns kryptografiska metoder som äger såna datorer också.
btw.
"Both RSA and ElGamal encryption have known attacks which are much faster than the brute force approach." - wikiartikeln
Per Andersson
> Den 24 mars 2010 16.03 skrev Per Andersson <avto...@gmail.com>:
>> Jo, men att brute-forca fram den ena ur den andra är ju ingen
>> matematisk relation.
>
> inte att lösa i polynomiell(?) tid i förhållande till inputet. Om man inte
> har en sån där datamaskin som alla forskar på, som vissa säger att NSA har
> (fet chans). Men det finns kryptografiska metoder som äger såna datorer
> också.
Det var primtalsfaktoriseringen jag undrade över. :-)
> btw.
> "Both RSA and ElGamal encryption have known attacks which are much faster
> than the brute force approach." - wikiartikeln
Ja, de är ganska intressanta
http://en.wikipedia.org/wiki/RSA#Timing_attacks
-- Per