Hard Live

CoppeRSA Lattice

70 points

120 Solves

Cryptography

Hard

digital_turtle

Community Rating: 4.42 / 5

There are plenty of bits of randomness in the key. This has to be secure!

I am so confident, that I am sharing a snippet of my implementation:

import random
base = random.getrandbits(2048)
p = next_prime(base + random.getrandbits(256))
q = next_prime(base + random.getrandbits(256))
n = p * q
e = 65537
print("e = ", e)
print("n = ", n)
c = power_mod(m, e, n)
print("c = ", c)

Output:

e = 65537
n = 8281850967132278399574272688766937486036646313403007679588335903785669628431708760927341727806006769095252325575815709840401878674105658204057327337750902945521512357960818523078486774689928139816732080923197367563639383252762498921096166065153092144335239373370093976823925031794323976150363874930075228846801224430767428594024165529140949082062667410186456029480046489969338885725614510660737026927443934115006027747874368836800022473917576424175601374800697491622086825964475396316066082109998646438504664272000556702241576240616765962934452557847306066736505798267513078073147161755828577875047115978481485076227911405625234425533967247248864837854031634968764570599279385827285321806293661331225163255461894680337693227417748934924109356565823327149859245521513696171473417470936260563397398387972467438182651142096935931112668743912944902147582538985769095457203775208567489073198557073226907349118348902079942096374377432431441166710584381655348979330535397040250376989291669788189409825278457889980676574146044704329826483808929549888234303934178478274711686806257841293265249466735277673158607466360053037971774844824065612178793324128914371112619033111301900922374201703477207948412866443213080633623441392016518823291181
c = 6407923537926201847312357068295079879508779752068254604904486842729636773279241546432035102141932853761974844472828552921133743850412718722424893044377874567625621282274625365299685502104113862870672461666586814138206797733946319875258776059721304226419810313489197076949529322847815009706727586961448584443159011118432142946962961532154723891985416387650240762711716865116844837968079333914181751979527853152286708153252001832721723040664452442266930832118353632114958540067674924812749763008217133300059446967170825813909142247660230309955433005706793802514554628379255160648976960069078223370104177403453404917998945232459801324103878906593528309460372271638119657797804398399482025063414403804134607772871958848100256643503372624214762343403925077455660522664025602043433142314759978192969519687720668535544914589329155338178120703060384042066182354031274600184116143293639032906542194564776766076911767759167772137229504115598174156646085123675283692418970988032320780636742598466655712520383055569607154074137271584433653335176877094399371749081016317705026349554938167377640856287458145646649292278971980553895419112860061073864077521131958519819285117031990498977039003918710661660868949818362940359852436185282868088342132

First 10 Solvers

Rank Username
1 ebouteillon
2 Ntoskrnl
3 zeek
4 oter
5 domi_roca

  • intelagent moderator badge ctflearn++ badge

    Protected

    [REDACTED] This comment is only shown to users who have solved this challenge.

    • digital_turtle

      Hi. Thank you for taking the time to review my challenge. I am not however able to read your message since the comment is protected...

      • intelagent moderator badge ctflearn++ badge

        I will fix that. It just said: "Hey, this challenge looks great! I will set a time on Twitter to release it. Thanks for contributing!"

  • ebouteillon

    Protected

    [REDACTED] This comment is only shown to users who have solved this challenge.

    • intelagent moderator badge ctflearn++ badge

      Protected

      [REDACTED] This comment is only shown to users who have solved this challenge.

      • ebouteillon

        Protected

        [REDACTED] This comment is only shown to users who have solved this challenge.

        • intelagent moderator badge ctflearn++ badge

          Gotcha! We will soon be releasing writeup support so everyone can keep track of their own methods and also share with others. I'll post about it on twitter tonight hopefully.

          • Caillou

            Hi. Old post but any idea of this project of writeup support?

            • intelagent moderator badge ctflearn++ badge

              Hey, sorry it has taken so long, I was abroad for several months, but should have some time in the near future to get back to it!

  • intelagent moderator badge ctflearn++ badge

    Protected

    [REDACTED] This comment is only shown to users who have solved this challenge.

    • domi_roca

      I have solved it that way too, that website has some very efficient algorithms, been always using it when I can't find anything on factordb

      • intelagent moderator badge ctflearn++ badge

        This challenge could be a lot more effective. I’m going to get in touch with the creator. We might need a larger N haha.

  • CapitalZer0

    Protected

    [REDACTED] This comment is only shown to users who have solved this challenge.

  • oter

    Great exercise, but quite challenging! Must admit I didn't understand everything that happened, but I learned a lot about RSA and Coppersmith's attack and LLL!

  • dani0104

    CTFlearn{n0t_th4t_s3cur3_4ft3r_4ll}

    • dani0104

      Whoops wrong box, plz delete this comment

  • M4DG0D

    I think this was a basic RSA and no need for Coppersmith attack. Yes but it urges you to read about that which is excellent.

  • IT_Oracle

    Fun challenge but a larger n is definitely needed to ensure that Coppersmith's is used.