Diskuze k úloze číslo 14
Toto fórum slouží výhradně k diskuzím o úloze číslo 14. Během hry je zakázáno diskutovat o zadání i řešení této úlohy kdekoliv jinde, než zde. K diskuzi o ostatních úlohách prosíme využijte jim příslušná fóra. Prosíme, nekažte hru ostatním!
Re: Diskuze k úloze číslo 14
Bilbo
(15. 11. 2009 - 5:40)
Sbalit(17)
At zije louskani 1024bitove RSA ... :)
No, konecne muzu jit spat ...
No, konecne muzu jit spat ...
Re: Diskuze k úloze číslo 14
anicka (org)
(15. 11. 2009 - 11:29)
Sbalit(16)
> At zije louskani 1024bitove RSA ... :)
>
> No, konecne muzu jit spat ...
No, s vědomím, že to někdo jiný dal a já ne, by se mi zas tak skvěle
neusínalo :-) Ve skutečnosti tohle RSA může dát méně práce než spousta
úloh předtím, ale jeden se holt nesmí leknout a vzdát to :-) Ty úlohy
mají jít vyřešit :-)
>
> No, konecne muzu jit spat ...
No, s vědomím, že to někdo jiný dal a já ne, by se mi zas tak skvěle
neusínalo :-) Ve skutečnosti tohle RSA může dát méně práce než spousta
úloh předtím, ale jeden se holt nesmí leknout a vzdát to :-) Ty úlohy
mají jít vyřešit :-)
Re: Diskuze k úloze číslo 14
Bilbo
(15. 11. 2009 - 14:38)
Sbalit(15)
Dal to nekdo ze zbylych tri uspesnych jinak nez pres zolika?
Me se osobne s vedomim ze ted uz mne nikdo po probdele noci ve vysledcich nepredbehne a ze zitra se mi to s mensi hladinou spankoveho deficitu bude resit lepe usinalo celkem dobre :)
A kdo tu mluvil o vzdavani? :)
Me se osobne s vedomim ze ted uz mne nikdo po probdele noci ve vysledcich nepredbehne a ze zitra se mi to s mensi hladinou spankoveho deficitu bude resit lepe usinalo celkem dobre :)
A kdo tu mluvil o vzdavani? :)
Re: Diskuze k úloze číslo 14
Michal Kubeček
(15. 11. 2009 - 15:27)
Sbalit(14)
On Sun, Nov 15, 2009 at 02:38:43PM +0100, Bilbo wrote:
> Dal to nekdo ze zbylych tri uspesnych jinak nez pres zolika?
Nevím :-) - nebo spíš :-(
Jednu chvíli jsem na tom dokonce byl tak, že k dokončení jsem potřeboval
buď vyřešit čtrnáctku (tj. pravděpodobně rozlousknout GPG) nebo se
dostat k třetí vedlejší úloze, což v tu chvíli znamenalo rozlousknout
MD5 hash. :-)
> Dal to nekdo ze zbylych tri uspesnych jinak nez pres zolika?
Nevím :-) - nebo spíš :-(
Jednu chvíli jsem na tom dokonce byl tak, že k dokončení jsem potřeboval
buď vyřešit čtrnáctku (tj. pravděpodobně rozlousknout GPG) nebo se
dostat k třetí vedlejší úloze, což v tu chvíli znamenalo rozlousknout
MD5 hash. :-)
Re: Diskuze k úloze číslo 14
Michal Kubeček
(15. 11. 2009 - 15:44)
Sbalit(1)
Akorát teď budu muset být opatrný a radši nečíst tuhle diskusi, abych se
nedozvěděl něco, co se zatím dozvědět nechci. Nebo aspoň ne odsud... :-)
nedozvěděl něco, co se zatím dozvědět nechci. Nebo aspoň ne odsud... :-)
Re: Diskuze k úloze číslo 14
anicka
(15. 11. 2009 - 16:02)
Sbalit(11)
Zatím je to 50:50, dvě řešení (obě s nápovědou na kuráž), dva žolíci. A tvrdne na ní celkem dost lidí, co už žolíky nemají a už si napsali o nápovědu, tak by se to snad brzy mohlo protrhnout.
Re: Diskuze k úloze číslo 14
Michal Kubeček
(15. 11. 2009 - 16:07)
Sbalit(10)
Takže rozumím-li tomu dobře, zatím to nikdo nevyřešil bez nápovědy? Tak
to se na to asi vrhnu hned... :-)
to se na to asi vrhnu hned... :-)
Re: Diskuze k úloze číslo 14
anicka (org)
(15. 11. 2009 - 16:17)
Sbalit(9)
> Takže rozumím-li tomu dobře, zatím to nikdo nevyřešil bez nápovědy? Tak
> to se na to asi vrhnu hned... :-)
Presne tak... aha, a tri zolici, dve uspesne napovedy.
> to se na to asi vrhnu hned... :-)
Presne tak... aha, a tri zolici, dve uspesne napovedy.
Re: Diskuze k úloze číslo 14
tomi
(15. 11. 2009 - 17:29)
Sbalit(8)
Jen tak mimochodem, kde byly ty další vedlejší úlohy? Já si všiml jen hashe, který jsem neprolomil (zkoušel jsem zhashovat celej */bin a potom "echo slovo" pro celej slovník) a potom to u těch štítků, ale to jsem zkoušel jen chvíli a pak se zase vrátil k řešení devítky.
Re: Diskuze k úloze číslo 14
Bilbo
(15. 11. 2009 - 17:35)
Sbalit(7)
Myslim ze je prilis brzo je prozrazovat, nekteri co sem dosli by treba chteli si je zkusit najit a vyresit ...
Jinak ten hash jsem taky neprolomil. Zatim :)
Jinak ten hash jsem taky neprolomil. Zatim :)
Re: Diskuze k úloze číslo 14
anicka (org)
(15. 11. 2009 - 17:46)
Sbalit(5)
> Myslim ze je prilis brzo je prozrazovat, nekteri co sem dosli by treba
> chteli si je zkusit najit a vyresit ...
Na druhou stranu, mozna se Vam muze hodit vedet, kolik jich je, abyste
vedeli, kdy prestat hledat. Je mi jasne, ze ne vsichni vitezove by to
hned ted vedet chteli... takze tady mate md5 ze spravneho cisla:
e4da3b7fbbce2345d7772b0674a318d5 ;D
> chteli si je zkusit najit a vyresit ...
Na druhou stranu, mozna se Vam muze hodit vedet, kolik jich je, abyste
vedeli, kdy prestat hledat. Je mi jasne, ze ne vsichni vitezove by to
hned ted vedet chteli... takze tady mate md5 ze spravneho cisla:
e4da3b7fbbce2345d7772b0674a318d5 ;D
Re: Diskuze k úloze číslo 14
tomi
(15. 11. 2009 - 17:55)
Sbalit(2)
Jo, dík. Asi se tím zkusím po večerech v týdnu probrat, dneska už to stačilo :-).
(btw, je správně, že žolíkem se člověk dostane i do fóra k řešení úlohy?) :-)
(btw, je správně, že žolíkem se člověk dostane i do fóra k řešení úlohy?) :-)
Re: Diskuze k úloze číslo 14
Robert-Antonio
(15. 11. 2009 - 20:02)
Sbalit(2)
Wow, tak to abych ještě hledal:)
Poslední dobou mám na hašování nějakou smůlu. Před týdnem jsem takhle zkoušel prolomit zaSHAšované souřadnice jedné geokešky, bohužel také neúspěšně. To zahašované heslo na vedlejší úlohu mi dlouho odolávalo, až jsem v pátek těsně před usnutím přišel, v čem bude háček :)
Poslední dobou mám na hašování nějakou smůlu. Před týdnem jsem takhle zkoušel prolomit zaSHAšované souřadnice jedné geokešky, bohužel také neúspěšně. To zahašované heslo na vedlejší úlohu mi dlouho odolávalo, až jsem v pátek těsně před usnutím přišel, v čem bude háček :)
Re: Diskuze k úloze číslo 14
Jirka Benc (org)
(15. 11. 2009 - 19:10)
Sbalit(1)
> Jednu chvíli jsem na tom dokonce byl tak, že k dokončení jsem potřeboval
> buď vyřešit čtrnáctku (tj. pravděpodobně rozlousknout GPG) nebo se
> dostat k třetí vedlejší úloze, což v tu chvíli znamenalo rozlousknout
> MD5 hash. :-)
Ano, toho jsme si přesně u tebe všimli a škodolibě se tím bavili :-)
> buď vyřešit čtrnáctku (tj. pravděpodobně rozlousknout GPG) nebo se
> dostat k třetí vedlejší úloze, což v tu chvíli znamenalo rozlousknout
> MD5 hash. :-)
Ano, toho jsme si přesně u tebe všimli a škodolibě se tím bavili :-)
Re: Diskuze k úloze číslo 14
tomi
(15. 11. 2009 - 14:32)
Sbalit(2)
Tak tohle bylo opravdu pěkné, škoda, že jsem potřeboval nápovědu na kuráž :-). Dělal to někdo z vás ručně, nebo jste taky nahardkódovali ty dvě prvočísla do zdrojáků gnupg?
Re: Diskuze k úloze číslo 14
petr.skovron
(15. 11. 2009 - 15:37)
Sbalit(1)
Taky me trochu mrzi, ze jsem potreboval napovedu na kuraz (mozna bych spis rekl, ze jeste ze mam takovou schopnost sebereflexe), a taky jsem p a q zadratoval do zdrojaku.
Prve (pred napovedou) se mi nechtelo do tech zdrojaku moc vrtat, ztracet spoustu casu bez valne nadeje na vysledek. Ale nakonec musim rict, ze je gpg napsane velmi prehledne.
Prve (pred napovedou) se mi nechtelo do tech zdrojaku moc vrtat, ztracet spoustu casu bez valne nadeje na vysledek. Ale nakonec musim rict, ze je gpg napsane velmi prehledne.
Re: Diskuze k úloze číslo 14
Robert-Antonio
(15. 11. 2009 - 19:55)
Sbalit(21)
Yabba-dabba-dooo! a je to v suchu:)
Ano, cracknutí RSA byl můj první nápad. Pokud jsi Aničko tím "bude se mi líbit" myslela crackování RSA na Haluzi '06, tak jsem si na to také vzpomněl, ale tam měli jen 304bitový kód. Poté, co jsem progooglil, že faktorizaci 1024bitové RSA nezvládají ani kolegové z NSA, jsem usoudil, že to asi správná cesta nebude a počkal si na nápovědu. Ta mi toho opravdu řekla:)
Ne, vážně, bez nápovědy bych opravdu nezkoušel, že prvočísla v privátním klíči vyberete tak dobře, že na ně bude fungovat Pollardův algoritmus. Moc jich takových není, a navíc jsem předpokládal, že GPG bude takováto prvočísla zahazovat (...ale teď vidím že minimálně v 1.4 to nedělá).
Možná větší problém než cracknout RSA bylo zapracovat to všecko do GPG. Prvočísla jsem měl hotová už před 6 hodinami a zbytek bylo podnětné prolézání zdrojáky, a podstrkování prvočísel a keyid :))
Ano, cracknutí RSA byl můj první nápad. Pokud jsi Aničko tím "bude se mi líbit" myslela crackování RSA na Haluzi '06, tak jsem si na to také vzpomněl, ale tam měli jen 304bitový kód. Poté, co jsem progooglil, že faktorizaci 1024bitové RSA nezvládají ani kolegové z NSA, jsem usoudil, že to asi správná cesta nebude a počkal si na nápovědu. Ta mi toho opravdu řekla:)
Ne, vážně, bez nápovědy bych opravdu nezkoušel, že prvočísla v privátním klíči vyberete tak dobře, že na ně bude fungovat Pollardův algoritmus. Moc jich takových není, a navíc jsem předpokládal, že GPG bude takováto prvočísla zahazovat (...ale teď vidím že minimálně v 1.4 to nedělá).
Možná větší problém než cracknout RSA bylo zapracovat to všecko do GPG. Prvočísla jsem měl hotová už před 6 hodinami a zbytek bylo podnětné prolézání zdrojáky, a podstrkování prvočísel a keyid :))
Re: Diskuze k úloze číslo 14
Martin Mares (org)
(15. 11. 2009 - 19:59)
Sbalit(4)
Pollardův algoritmus ani nepotřebuješ, menší z obou prvočísel je velké řádově 10^9,
takže se dá najít zkusmo.
(Jinak až sepíšeme řešení, dočtete se, jak měla úloha vypadat původně ;) )
takže se dá najít zkusmo.
(Jinak až sepíšeme řešení, dočtete se, jak měla úloha vypadat původně ;) )
Re: Diskuze k úloze číslo 14
Robert-Antonio
(15. 11. 2009 - 20:06)
Sbalit(3)
Jenže jak mám vědět předem, že jste jedno prvočíslo zvolili úmyslně malé? Měl jsem místo Pollarda použít msieve a modlit se, aby doběhl aspoň do konce čtvrtohor?
Re: Diskuze k úloze číslo 14
Martin Mares (org)
(15. 11. 2009 - 20:07)
Sbalit(2)
Možná se dalo tušit, že jsme nepoužili dvě libovolná 512-bitová prvočísla,
tak drsní zase nejsme :-)
tak drsní zase nejsme :-)
Re: Diskuze k úloze číslo 14
Robert-Antonio
(15. 11. 2009 - 20:12)
Sbalit(1)
To jistě, ale až po nápovědě, že jde opravdu o cracknutí RSA.
A když jste ještě v nápovědě psali o žhavení clusterů, tak jsem vážně uvažoval o tom, že chcete, abychom si zkusili naprogramovat distribuované výpočty:)
A když jste ještě v nápovědě psali o žhavení clusterů, tak jsem vážně uvažoval o tom, že chcete, abychom si zkusili naprogramovat distribuované výpočty:)
Re: Diskuze k úloze číslo 14
tomi
(15. 11. 2009 - 20:03)
Sbalit(1)
GnuPG při generování prvočísel pro RSA generuje čísla velká zhruba nbits/2, takovéhle dvě by opravdu samo neudělalo. Já teda žádný algoritmus neprogramoval, prostě jsem to číslo zadal na webu kamsi a vypadly dvě prvočísla. Později se ukázalo, že ten web používá PARI/GP, který jsem znal, ale neměl nainstalovaný.
K tomu keyid: stačí při dešifrování zadat --try-all-secrets, keyid může být absolutně jakékoliv.
K tomu keyid: stačí při dešifrování zadat --try-all-secrets, keyid může být absolutně jakékoliv.
Re: Diskuze k úloze číslo 14
anicka (org)
(15. 11. 2009 - 20:09)
Sbalit(15)
> Yabba-dabba-dooo! a je to v suchu:) Ano, cracknutí RSA byl můj první
> nápad. Pokud jsi Aničko tím "bude se mi líbit" myslela crackování RSA
Gratuluju! Na Haluzi jsem nebyla, ale když jsi přes ty technoidní
šifrovačky, měla jsem pocit, že by se Ti to mělo líbit :-)
Jak už jsem říkala Xofovi, nakonec jste k tomu přišli ještě docela
lacino: Původně jsem chtěla udělat ono pověstné ssh s klíčem z Debianu,
ale to se jevilo být jako příliš velká šílenost už ve fázi plánování.
Pak jsem dlouho laškovala s krátkými klíči, což by většina openssl
zvládla, jen v podepisování má nepříjemný limit - mimochodem, je to
bastl chlupatá a zajímavá úloha je už přijít na to, jaký vlastně.
Nu a pak se do toho vložil MJ s nápadem použít gpg... zase jsme si
prošli kolečko krátký klíč (smůla, počítá s limitem podle RFC), klíč
jakožto druhá mocnina prvočísla (tady byste si museli ještě ručně
spočítat Eulerovu funkci, zatímco současná verze žádné velké znalosti RSA
nevyžaduje - ale taky smůla, gpg používá nějaké optimalizace, které nám
udělaly čáru přes rozpočet). Takže to vlastně nakonec bylo docela
jednoduché... :-D Všichni jsme byli napnutí jak kšandy, jestli to někdo
dá a nebo jestli to všichni vyžolíkují. A ještě všichni napnutí jsme,
jestli se najde někdo, kdo nevyměkne a dá to i bez povzbuzení, protože
nápověda skoro nic jiného nedělá :-)
A jasně, že jsme to vyráběli úplně stejně, jako jste to vy luštili -
díky tomu MJ objevil tu nedokumentovanou věc, co jste potkali v
nápovědě.
> nápad. Pokud jsi Aničko tím "bude se mi líbit" myslela crackování RSA
Gratuluju! Na Haluzi jsem nebyla, ale když jsi přes ty technoidní
šifrovačky, měla jsem pocit, že by se Ti to mělo líbit :-)
Jak už jsem říkala Xofovi, nakonec jste k tomu přišli ještě docela
lacino: Původně jsem chtěla udělat ono pověstné ssh s klíčem z Debianu,
ale to se jevilo být jako příliš velká šílenost už ve fázi plánování.
Pak jsem dlouho laškovala s krátkými klíči, což by většina openssl
zvládla, jen v podepisování má nepříjemný limit - mimochodem, je to
bastl chlupatá a zajímavá úloha je už přijít na to, jaký vlastně.
Nu a pak se do toho vložil MJ s nápadem použít gpg... zase jsme si
prošli kolečko krátký klíč (smůla, počítá s limitem podle RFC), klíč
jakožto druhá mocnina prvočísla (tady byste si museli ještě ručně
spočítat Eulerovu funkci, zatímco současná verze žádné velké znalosti RSA
nevyžaduje - ale taky smůla, gpg používá nějaké optimalizace, které nám
udělaly čáru přes rozpočet). Takže to vlastně nakonec bylo docela
jednoduché... :-D Všichni jsme byli napnutí jak kšandy, jestli to někdo
dá a nebo jestli to všichni vyžolíkují. A ještě všichni napnutí jsme,
jestli se najde někdo, kdo nevyměkne a dá to i bez povzbuzení, protože
nápověda skoro nic jiného nedělá :-)
A jasně, že jsme to vyráběli úplně stejně, jako jste to vy luštili -
díky tomu MJ objevil tu nedokumentovanou věc, co jste potkali v
nápovědě.
Re: Diskuze k úloze číslo 14
tomi
(15. 11. 2009 - 20:12)
Sbalit(1)
(jen btw, v 1.4.10 to v manu je, akorát už tam není napsaný, co který číslo znamená)
Re: Diskuze k úloze číslo 14
Robert-Antonio
(15. 11. 2009 - 20:23)
Sbalit(13)
To je otázka, zdali to někdo dá bez nápovědy. Protože to vyžaduje netriviální předpoklad, že "orgové nejsou až takové svině"* a uměle tu RSA zjednodušší. Bez tohoto předpokladu je logická úvaha: 1024bitovou RSA v současnosti prolomit nejde -> šifra bude v něčem jiném.
Ale neber to jako kritiku, myslím že úloha dokonale splnila svůj účel - osvěžit si RSA, zkusit faktorizovat velká čísla a prohrabat se zdrojáky GPG.
BTW i přes zálibu v Matrixech a spol. nejsem hacker a můj první a poslední hack byl do sítě FELAN na základce (prostě během autoexecu zmáčknout v pravou chvíli ctrl-c a měla jsi i bez uživatelského účtu přístup na lokální disk s hrami :)))
* Půvabné je, že na fóru Tmou jsme diskutovali šifru, kde naopak k správnému vyřešení bylo třeba předpokládat, že orgové JSOU svině a do jedné indicie zabudují dvě šifry zároveň:)
Ale neber to jako kritiku, myslím že úloha dokonale splnila svůj účel - osvěžit si RSA, zkusit faktorizovat velká čísla a prohrabat se zdrojáky GPG.
BTW i přes zálibu v Matrixech a spol. nejsem hacker a můj první a poslední hack byl do sítě FELAN na základce (prostě během autoexecu zmáčknout v pravou chvíli ctrl-c a měla jsi i bez uživatelského účtu přístup na lokální disk s hrami :)))
* Půvabné je, že na fóru Tmou jsme diskutovali šifru, kde naopak k správnému vyřešení bylo třeba předpokládat, že orgové JSOU svině a do jedné indicie zabudují dvě šifry zároveň:)
Re: Diskuze k úloze číslo 14
anicka (org)
(15. 11. 2009 - 20:28)
Sbalit(12)
> To je otázka, zdali to někdo dá bez nápovědy. Protože to vyžaduje
> netriviální předpoklad, že "orgové nejsou až takové svině"* a uměle tu
> RSA zjednodušší. Bez tohoto předpokladu je logická úvaha: 1024bitovou
> RSA v současnosti prolomit nejde -> šifra bude v něčem jiném.
To jsme předpokládali, a proto jsme vložili přímo do zadání nápovědu ve
formě robůtkova maniodepresivního deníčku:
Samozrejme naprosto zbytecne, protoze na to, aby nekdo rozlousknul
takovouhle jednoduchou sifru, staci, aby mel sotva ctyriasedesatinu me
mozkove kapacity. Driv nebo pozdeji na to urcite nekdo prijde a to bude
poprask.
Asi jsme ale neodhadli situaci a pořád to ještě bylo málo výmluvné :(
> netriviální předpoklad, že "orgové nejsou až takové svině"* a uměle tu
> RSA zjednodušší. Bez tohoto předpokladu je logická úvaha: 1024bitovou
> RSA v současnosti prolomit nejde -> šifra bude v něčem jiném.
To jsme předpokládali, a proto jsme vložili přímo do zadání nápovědu ve
formě robůtkova maniodepresivního deníčku:
Samozrejme naprosto zbytecne, protoze na to, aby nekdo rozlousknul
takovouhle jednoduchou sifru, staci, aby mel sotva ctyriasedesatinu me
mozkove kapacity. Driv nebo pozdeji na to urcite nekdo prijde a to bude
poprask.
Asi jsme ale neodhadli situaci a pořád to ještě bylo málo výmluvné :(
Re: Diskuze k úloze číslo 14
Bilbo
(15. 11. 2009 - 22:03)
Sbalit(11)
> 1024bitovou RSA v současnosti prolomit nejde -> šifra bude v něčem jiném.
Taky jsem dost dlouho hledal jinde, protoze uz 512bitu je dost na hranici prolomitelnosti (pokud bych chtel prolomit 512bitu do konce souteze potreboval bych minimalne par set az tisic pocitacu) a 1024 je soucasnou vypocetni silou prakticky neprolomitelne. Zkousel jsem jestli muzou byt nejake informace skryte v hlavice mailu, v textu, zkousel jsem jestli nebudou uvnit paketu nejake skryte informace (mohla by tam byt platna hlavicka a telo pak nahrazeno necim jinym) ... a nic.
Taky jsem pomerne rychle zjistil ze GPG zprava ma dva pakety - prvni je RSA ciphertext, kde krome KEYID a hlavicky je ulozene m^e mod n (aneb ciphertext), druhy paket je symetricky sifrovany (takze pokud se louskne RSA, tak rozsifrovat druhou cast bude jiz trivialni, neb v te prvni je session key, ale do te doby ho muzu vesele ignorovat)
> To jsme předpokládali, a proto jsme vložili přímo do zadání nápovědu ve
> formě robůtkova maniodepresivního deníčku:
Tusil jsem ze ta sifra bude asi nejak oslabena, jinak by to bylo neresitelne, ale nebyl k dispozici ani verejny klic, kterym to bylo zasifrovane (zkousel jsem hledat to keyid ruzne ale nic, ostatne ani jsem necekal ze verejny klic fiktivniho Niela Ambroze bude viset nekde na netu), takze zadne e a n ktere by slo rovnou faktorizovat.
Vim:
ciphertext = m^e mod n
vim ze p*q=n a 0 < ciphertext < n, e= pravdepodobne 65537
Na ziskani privatniho klice a rozsifrovani potrebuju p a q, ktere vyfaktorizuji z n.
Jenze jak zjistit n? Vim ze je "o neco vetsi" nez ciphertext, ale to muze byt jakekoliv cislo mezi cipertextem a cca 2^1024. Zkousel jsem hledat zminky o nejakem utoku na ciphertext v RSA, ale nenasel jsem nic pouzitelnyho.
No a tady jsem se zasek. Nakonec jsem pouzil zolika...
Taky jsem dost dlouho hledal jinde, protoze uz 512bitu je dost na hranici prolomitelnosti (pokud bych chtel prolomit 512bitu do konce souteze potreboval bych minimalne par set az tisic pocitacu) a 1024 je soucasnou vypocetni silou prakticky neprolomitelne. Zkousel jsem jestli muzou byt nejake informace skryte v hlavice mailu, v textu, zkousel jsem jestli nebudou uvnit paketu nejake skryte informace (mohla by tam byt platna hlavicka a telo pak nahrazeno necim jinym) ... a nic.
Taky jsem pomerne rychle zjistil ze GPG zprava ma dva pakety - prvni je RSA ciphertext, kde krome KEYID a hlavicky je ulozene m^e mod n (aneb ciphertext), druhy paket je symetricky sifrovany (takze pokud se louskne RSA, tak rozsifrovat druhou cast bude jiz trivialni, neb v te prvni je session key, ale do te doby ho muzu vesele ignorovat)
> To jsme předpokládali, a proto jsme vložili přímo do zadání nápovědu ve
> formě robůtkova maniodepresivního deníčku:
Tusil jsem ze ta sifra bude asi nejak oslabena, jinak by to bylo neresitelne, ale nebyl k dispozici ani verejny klic, kterym to bylo zasifrovane (zkousel jsem hledat to keyid ruzne ale nic, ostatne ani jsem necekal ze verejny klic fiktivniho Niela Ambroze bude viset nekde na netu), takze zadne e a n ktere by slo rovnou faktorizovat.
Vim:
ciphertext = m^e mod n
vim ze p*q=n a 0 < ciphertext < n, e= pravdepodobne 65537
Na ziskani privatniho klice a rozsifrovani potrebuju p a q, ktere vyfaktorizuji z n.
Jenze jak zjistit n? Vim ze je "o neco vetsi" nez ciphertext, ale to muze byt jakekoliv cislo mezi cipertextem a cca 2^1024. Zkousel jsem hledat zminky o nejakem utoku na ciphertext v RSA, ale nenasel jsem nic pouzitelnyho.
No a tady jsem se zasek. Nakonec jsem pouzil zolika...
Re: Diskuze k úloze číslo 14
Martin Mares (org)
(15. 11. 2009 - 22:07)
Sbalit(4)
> ale nebyl k dispozici ani verejny klic, kterym to bylo zasifrovane
A zkoušel ses ptát keyserverů? Jak ty na pgp.net, tak ty staré na mit.edu
by o Nielově klíči měly vědět. Nebo se zeptat Niela? :-)
A zkoušel ses ptát keyserverů? Jak ty na pgp.net, tak ty staré na mit.edu
by o Nielově klíči měly vědět. Nebo se zeptat Niela? :-)
Re: Diskuze k úloze číslo 14
Robert-Antonio
(16. 11. 2009 - 12:04)
Sbalit(3)
> Nebo se zeptat Niela? :-)
Genau. Díky tomu jsem napsal svůj první phishningový mail v životě, máte ho v Nielově schránce:) Ale než mi přišla odpověď, našel jsem Nielův klíč také na keyserveru.
Genau. Díky tomu jsem napsal svůj první phishningový mail v životě, máte ho v Nielově schránce:) Ale než mi přišla odpověď, našel jsem Nielův klíč také na keyserveru.
Re: Diskuze k úloze číslo 14
Jirka Benc (org)
(16. 11. 2009 - 12:55)
Sbalit(2)
To my samozřejmě víme, velmi jsme se u něj bavili (a při odpovídání na něj také). Škoda, že v pravidlech nemáme nic o časovém bonusu za pobavení orgů :-)
Re: Diskuze k úloze číslo 14
anicka (org)
(16. 11. 2009 - 13:02)
Sbalit(1)
> To my samozřejmě víme, velmi jsme se u něj bavili (a při odpovídání na
> něj také). Škoda, že v pravidlech nemáme nic o časovém bonusu za
> pobavení orgů :-)
Měli bychom ještě dodat, že nebyl jediný, ba ani první, ale tomu druhému
ještě ani mail Nielovi nepomohl :-) A zatímco nad tím prvním mailem jsem
se jenom tak normálně chechtala, nad Marjánkou mi v tom záchvatu smíchu
tekly slzy :-D
> něj také). Škoda, že v pravidlech nemáme nic o časovém bonusu za
> pobavení orgů :-)
Měli bychom ještě dodat, že nebyl jediný, ba ani první, ale tomu druhému
ještě ani mail Nielovi nepomohl :-) A zatímco nad tím prvním mailem jsem
se jenom tak normálně chechtala, nad Marjánkou mi v tom záchvatu smíchu
tekly slzy :-D
Re: Diskuze k úloze číslo 14
anicka (org)
(15. 11. 2009 - 22:08)
Sbalit(6)
> zasifrovane (zkousel jsem hledat to keyid ruzne ale nic, ostatne ani
> jsem necekal ze verejny klic fiktivniho Niela Ambroze bude viset nekde
> na netu)
Aha, dost me prekvapilo, zes to ani nezkusil. Snazili jsme se ho nacpat
na keyservery dost brzy na to, aby se stihl rozsirit a pevne doufame, ze
od zacatku hry je vsude. Podepsany pulkou orgu Po drate ;-)
Predstavovali jsme si, ze ho ucastnici ziskaji z verejneho keyserveru.
> jsem necekal ze verejny klic fiktivniho Niela Ambroze bude viset nekde
> na netu)
Aha, dost me prekvapilo, zes to ani nezkusil. Snazili jsme se ho nacpat
na keyservery dost brzy na to, aby se stihl rozsirit a pevne doufame, ze
od zacatku hry je vsude. Podepsany pulkou orgu Po drate ;-)
Predstavovali jsme si, ze ho ucastnici ziskaji z verejneho keyserveru.
Re: Diskuze k úloze číslo 14
tomi
(15. 11. 2009 - 22:10)
Sbalit(1)
Já dal prostě gpg --search-keys a fungovalo ok.
Re: Diskuze k úloze číslo 14
Bilbo
(15. 11. 2009 - 22:27)
Sbalit(4)
Ale zkusil jsem to. Nejdriv jsem zkusil dat keyid (kratke i dlouhe) do googlu jestli nahodou rovnou nevyplave (nevyplavalo) - tak jsem pak zkouset najit klice Martina Marese, ale pak jsem si uvedomil ze je to blbost, neb on je odesilatel, tak jsem zkousel keyserver na kterem mel on sam klic ulozeny (podezrival jsem ho, ze kdyz v te uloze ma prsty, ze by tam mohl pripadne i ten klic nahrat, POKUD ma byt klic k nalezeni) a pak dalsi asi dva nebo tri servery
(i ten na mit.edu: http://pgp.mit.edu:11371/pks/lookup?search=BD50C1B8&op=index -> nic)
a nic ... zkousel jsem jeste prolezt web podrate.cz jestli tam nekde nebude neco jako "robutkuv GPG klic", ale taky nic, tak jsem usoudil ze klic proste neni a zacal jsem tu zpravu pitvat bez klice.
(i ten na mit.edu: http://pgp.mit.edu:11371/pks/lookup?search=BD50C1B8&op=index -> nic)
a nic ... zkousel jsem jeste prolezt web podrate.cz jestli tam nekde nebude neco jako "robutkuv GPG klic", ale taky nic, tak jsem usoudil ze klic proste neni a zacal jsem tu zpravu pitvat bez klice.
Re: Diskuze k úloze číslo 14
Bilbo
(15. 11. 2009 - 22:28)
Sbalit(3)
Teda http://pgp.mit.edu:11371/pks/lookup?search=0xFA2550FD&op=index .. tamten odkaz jsem zkousel jiny klic. Oboji nic...
Re: Diskuze k úloze číslo 14
Robert-Antonio
(15. 11. 2009 - 21:40)
Sbalit(1)
Hele, že vy jste s rootem domluvení?
http://www.root.cz/clanky/gpg-sifrovani-otevrene-a-bezpecne/
:))
http://www.root.cz/clanky/gpg-sifrovani-otevrene-a-bezpecne/
:))
Re: Diskuze k úloze číslo 14
Bilbo
(15. 11. 2009 - 23:01)
Sbalit(1)
Tak ted kdyz jsem nasel verejny klic tak faktorizace je uz jen zalezitosti chvilky (pustil jsem to a dobehlo to ani ne za vterinu) ... takze si pujdu precist co je uvnitr :)
Re: Diskuze k úloze číslo 14
Martin "Marble" Beránek
(16. 11. 2009 - 10:17)
Sbalit(5)
Tak už jsem si 14 také vyřešil "poctivě". Alespon důvod pročíst si RFC 2440. :) Zkoušel jsem si to kompletně došifrovat "ručně" v calc-u (debianí balíček apcalc), což fungovalo pěkně až po symetricky šifrovaná data. Tam jsem na tom AESku nějak zadřel, takže nakonec gpg-čkem. Ale když už jsme měl dešifrovaný symetrický klíč, tak jsme si ho jen zpátky zašifroval vlastním klíčem a přepsal v původní zprávě.
Ad žolík -- ono už tím, že je to 14. úloha to používání žolíků dost nabízí. Koneckonců co lepšího se získaným (anebo skorozískaným) žolíkem těsně před koncem hry, zvlášt když úloha vypadá víc opruzovatě, než zajímavě.
Ad žolík -- ono už tím, že je to 14. úloha to používání žolíků dost nabízí. Koneckonců co lepšího se získaným (anebo skorozískaným) žolíkem těsně před koncem hry, zvlášt když úloha vypadá víc opruzovatě, než zajímavě.
Re: Diskuze k úloze číslo 14
pht
(18. 11. 2009 - 19:56)
Sbalit(4)
Myslím, že ten koncept žolíků je trochu od věci. Vedlejší úlohy by mohly zvýhodňovat hráče trochu jinak, např. se započítat do pořadí. Takhle to akorát nutí udělat N-K hlavních úloh + 3K z M vedlejších, místo aby si to člověk vychutnal všechno.
Re: Diskuze k úloze číslo 14
Michal Kubeček
(19. 11. 2009 - 14:32)
Sbalit(3)
Zase tak dramaticky bych to neviděl. Jednak z vzhledem k tomu, že m=5,
je k<=1. Jednak koncept žolíků fungoval teprve podruhé a poprvé
k žádnému masivnímu "zneužívání" nedošlo, z prvních 21 použil žolíka jen
jeden.
Navíc jsem přesvědčen, že i tentokrát, kdybych místo hledání všemožných
způsobů, jak se tomu vyhnout, udělal rovnou to, co jsem tušil, že se ve
čtrnáctce chce, vyřešil bych ji rychleji, než kolik času jsem strávil
různými slepými uličkami a hledáním vedlejších úloh.
Ale samozřejmě by se dalo uvažovat o tom, že žolíka nebude možné použít
u posledních úloh nebo že bude "dražší" (např. na přeskočení úloh 9-11
budou potřeba čtyři vedlejší úlohy a na úlohy 12-14 pět).
Zase tak dramaticky bych to neviděl. Jednak z vzhledem k tomu, že m=5,
je k<=1. Jednak koncept žolíků fungoval teprve podruhé a poprvé
k žádnému masivnímu "zneužívání" nedošlo, z prvních 21 použil žolíka jen
jeden.
Navíc jsem přesvědčen, že i tentokrát, kdybych místo hledání všemožných
způsobů, jak se tomu vyhnout, udělal rovnou to, co jsem tušil, že se ve
čtrnáctce chce, vyřešil bych ji rychleji, než kolik času jsem strávil
různými slepými uličkami a hledáním vedlejších úloh.
Ale samozřejmě by se dalo uvažovat o tom, že žolíka nebude možné použít
u posledních úloh nebo že bude "dražší" (např. na přeskočení úloh 9-11
budou potřeba čtyři vedlejší úlohy a na úlohy 12-14 pět).
Re: Diskuze k úloze číslo 14
anicka (org)
(19. 11. 2009 - 14:36)
Sbalit(2)
> Ale samozřejmě by se dalo uvažovat o tom, že žolíka nebude možné použít
> u posledních úloh nebo že bude "dražší" (např. na přeskočení úloh 9-11
> budou potřeba čtyři vedlejší úlohy a na úlohy 12-14 pět).
Určitě máme v plánu o konceptu vedlejších úloh a žolíků před příští hrou
pouvažovat, už teď se sešlo několik zajímavých návrhů na změny... takže
je možné, že se příště nějaké změny dočkáte. A Niela s jeho nápady
zkusíme přehlasovat :D
> u posledních úloh nebo že bude "dražší" (např. na přeskočení úloh 9-11
> budou potřeba čtyři vedlejší úlohy a na úlohy 12-14 pět).
Určitě máme v plánu o konceptu vedlejších úloh a žolíků před příští hrou
pouvažovat, už teď se sešlo několik zajímavých návrhů na změny... takže
je možné, že se příště nějaké změny dočkáte. A Niela s jeho nápady
zkusíme přehlasovat :D
Re: Diskuze k úloze číslo 14
Bilbo
(20. 11. 2009 - 2:38)
Sbalit(1)
Šlo by třeba udělat to, že za žolíka by byla "jen" zadarmo nápověda (tedy bez časového postihu) - což by šlo pochopitelně jen u úloh s nápovědou a to poté, co přijde na ní nabídka. Případně by mohla být speciální "žolíková" nápověda ke každé úloze, případně i o něco nápovědovější než klasická nápověda, takže by pak žolík hodně pomohl, ale sám o sobě úlohu nevyřešil. A pak by mohla být proti bezmyšlenkovému použití žolíka např. limit, kdy by šel použít nejdříve 30 minut po obdržení zadání.
Tím by se zamezilo i zneužití typu "mám žolíka a poslední úlohu, tak pošlu žolíka, 'vyhraju' a pak si ji půjdu v klidu louskat"
Třeba u 11. člověka v pořadí je mezi zadáním poslední úlohy a použitím žolíka pouhé 4 minuty ...
Pokud by nešel použít u posledních úloh, tak by se asi jen docílilo toho, že někteří ho bez rozmyslu použijí u poslední úlohy, kde to ještě jde.
Tím by se zamezilo i zneužití typu "mám žolíka a poslední úlohu, tak pošlu žolíka, 'vyhraju' a pak si ji půjdu v klidu louskat"
Třeba u 11. člověka v pořadí je mezi zadáním poslední úlohy a použitím žolíka pouhé 4 minuty ...
Pokud by nešel použít u posledních úloh, tak by se asi jen docílilo toho, že někteří ho bez rozmyslu použijí u poslední úlohy, kde to ještě jde.
Re: Diskuze k úloze číslo 14
george.gabriel
(17. 11. 2009 - 18:16)
Sbalit(2)
No faktorizaci klíče jsem dal už v první hodině. Ale pak jsem se vydal špatnou cestou - mám klíč tak to lousknu vlastním programem. To mě stálo 3 hodiny a stejně jsem se nedostal nikam a už jsem musel spát. Dneska po návštěvě babiček a kafíčka to byla otázka na hodinu - upravit gpg zdrojáky aby vygenerovali niamův klíč a změna hashe klíče ve zprávě. Hold škoda té slepé uličky.
Díky všem orgům za pěknou soutěž.
Ještě večer zkusím poslední (mě známou) vedlejší úlohu.....
Díky všem orgům za pěknou soutěž.
Ještě večer zkusím poslední (mě známou) vedlejší úlohu.....
Re: Diskuze k úloze číslo 14
Michal Kubeček
(17. 11. 2009 - 18:29)
Sbalit(1)
To nebyla nutně slepá ulička, dalo se to řešit i tak - podle RFC 4880
rozebrat klíč, dopočítat tajné informace, z nich spočítat session key
a pak spustit gpg s parametrem --override-session-key (takže ani nebylo
potřeba patchovat gpg).
rozebrat klíč, dopočítat tajné informace, z nich spočítat session key
a pak spustit gpg s parametrem --override-session-key (takže ani nebylo
potřeba patchovat gpg).