Débriefons…

Suite à la publication de la solution de challenge dans le MISC 73, nous nous proposons de conclure nos « recherches » et de factoriser la clé.

Dans son excellent article, le dompteur du challenge nous révèle qu’il fallait utiliser la méthode de factorisation P-1 de Pollard, vous savez celle où on tire profit de la friabilité de \phi(N).

Une fois que l’on sait cela, bah on fait ce qu’on sait faire de mieux : On bourrine… avec plus ou moins de finesse selon l’envie !

article-1082530-025611A7000005DC-977_468x315_popup

Nous obtenons alors le sesam tant attendu au bout de quelques heures (dérisoire par rapport aux semaines de calculs dépensés sur l’ECM lors de nos dernières tentatives).

Voici donc sans plus attendre la factorisation de cette p@#$%? de clé :

e   = 55348894806792612385414141451787827164645579309253228259335388271531487688039176095798120334501737367929748780052913670047188633808269373684030860483710969522003244423539306576623451027710592450713527715761004175586184817845680079127215619182378459242790668408608105750993309062249891306595047555936346734129994415037859873909247513518274701184001464686480163921256329289508829839879753067244532945006021175357093587634926430358770139715429032916952530663764121347143956641813414748473080919356806936961275769175903048941713499603531617658490435835866312975082993948236390280325535853182657204649112272207269007319129184397623931685360042465791404601791609185105619561250084631693965436104417064750736415034025598286506878081068717741073248839281492348549744603642550201288803237637498841394771273374256689836421271352768040314886778360408329008976174040904644371229683916605813548812954309687439361997174175029716933312924343891519849173182882767689231388532184646433042232550778109223395385517477187363775191992296325682996633136917903652328141171052722876002748311800181737316584093085625724914482170898100708094101688003217179221527719663974368485319818515338929020775698617091941580191761053043385463521118302031231220201634321
N   = 534678124722394890190402372350513358782337844848542965431160781496244441799002077160558946183719310184244104065359235053254710890066763140816078380278818747093517754630446486770511868265257786204674562839292200223909424213512126783602354757108901857452050587442891267767707264371689441037029754151422691444818751259519121668777067499262280066710257872381071416070402862768554512827217593787752778000697558592272925154681925169621862523913683587875598475720804762089544627483464474450871170515811658766329397799425886785775789388087086972448972098892373082500203087433596370445414815760374976437727290594488774680978908481550278294670417104486367845939819208657548206127498798782859967340625404245085451825938064773899937948709702153798441490033666837432527369347880332861002872050467103284623923562174874539942453739027593900063358540109709065465854390378684857666679564202335259763507862477309333071803208731719701726711869514696555505398161663811222139329805329118874154096177673098141294980248505369231289246196294531146957300315110309022439374615041665752448559592788592974232391016540756702855961671623284330070505719452595990653598817902636353291503648414423926856472727242293586720421200173659920007595323901524116824421073459
P   = 21823376410944773266308691264885661982533450395919921036186085854960786112444016345914488797661941485166644294734279212753759795691608350422011315600813563116083687879184569618458202603499954302017170425699951282620728692627064475135369629694846070310149676377738944852130128941950641868258746336196340443034897101610319329960729064977772690504064727787668539223681842782899107285246287888403285528010998749932007076673442916842324413246889045725445722746387751163195942856164202210060225032107865667568873998709217982710064430862508151132572592070347909900153157597693713968557156342425392011804672000000000000000001
Q   = 24500247562711938362025780689766610052896562428039532233302358937128314627060109580996866229968599680069679805646580518434714656424332827362887100094929490451683897600505652591845458557059717384810889756146324740273990707771374302844351562005122484601622413505924036189421547334217790887532028333272450470026422274928740126547324513447554746195839805614700807740358379495354932780689384316768456572706434311285921706640618829625016887299523517374007549491885876078015942086747534816778183378231953005290876265818572091088576265819730817021778073957680859283121817960901143926936874199076717523923453524116824421073459
Phi = 534678124722394890190402372350513358782337844848542965431160781496244441799002077160558946183719310184244104065359235053254710890066763140816078380278818747093517754630446486770511868265257786204674562839292200223909424213512126783602354757108901857452050587442891267767707264371689441037029754151422691444818751259519121668777067499262280066710257872381071416070402862768554512827217593787752778000697558592272925154681925169621862523913683587875598475720804762089544627483464474450871170515811658766329397799425886785775789388087086972448972098892373082500203087433596370445414815760374976437727290594488774680978862157926304637958788770014413193667783778644724246674229310338067878239885900119158540470910434232734701624609321294067253015581550896254742470932184589807435104464987413062413619901014314868255625678845747624040463820709310626687874669186984889111767792112451596782466310801033164639047417957050232935798808195320016445941653610232796811893105424585471784749213632875863040940182569697026117504095577098085739371531796247275972033314495253189349106320550319346991179131597844965829123263212944511397645969188068200579800177205954114323349297748395898087289452266734991862525706143118417898059595776000000000000000000
d   = 52990099860402129572942075649291370306230407802382221270791472917218879216764849336688684639406652814776974001270474779639651230192764123670323637321171897859761291433766230006398872142511875726486377327044124521551351133183118443183147580699665441606886422461868378491364605025888676331764107928102497621376670469650660427955083207855006097790820171378464706208479740147677557556376376492144489966652273494288175058270681816450659791856590488382875255015110601316551853994358593069854718302789118736637119704576787594019547761845175344743143021320782814721733183789579234425996737293059722405487361440783938180700191660537228691327572503653096943187593536789241859102054630445634083094785760902257573138810182790350254906072412402778060383443096865017907496042629052145588176563707259021560313364035473698623833762467500057056243025195522525426037723132684443434035611810327893828605544188498753699452728109929579276384166285294906450645945255172278914300294248076873630065264032542273181177942398319781335360339715721970055752142105075344446107727615562105298231407860230736757904189781123339596846826568860265837287827352551853733207108443118877644961398955817699959593133247698734704371278313014130144254855799349685873477220081

On notera cependant que tout cela ne nous explique pas pourquoi les concepteurs nous ont choisi un exposant public inhabituel (et surtout très grand). Peut être pour nous induire en erreur, si c’est le cas, cela a parfaitement fonctionné pour nous.

Quoiqu’il en soit, ce fut une épreuve intellectuelle à la fois stimulante et intéressante : On en redemanderait presque…

Publicités

A propos JoMendes

Amateur de mathématiques et d'hexadécimal. Je m'intéresse de près ou de loin suivant mon niveau à tous les sujets de sécurité de l'information.
Cet article, publié dans Challenge ANSSI, Cryptographie Asymétrique, est tagué , , . Ajoutez ce permalien à vos favoris.

2 commentaires pour Débriefons…

  1. th. TV dit :

    Bonjour
    Pourriez vous me dire combien vous avez utilisé de RAM pour factoriser le nombre? Car mon pc a essayé avec pari gp et 4go de ram, mais il avait besoin de plus ….
    Merci et bravo pour vos tentatives…
    Ah oui, si quelqu’un a une idée de comment le poème d’hérédia était crypté, je suis preneur, car j’ai passé quelques (dizaines) d’heures dessus sans grands résultats (si ce n’est qu’on pouvait le deviner).

    • JoMendes dit :

      8 Go de RAM sur notre pc ont permis de casser la clé. En utilisant SAGE, comme suggéré ca va vite (3h), avec YAFU ca fonctionne également mais il faut alors beaucoup plus de temps (9 semaines).

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s