PecanPlus - 2025

Incorrect Implimentation of RSA

By Raahguu (Joshua Finlayson)3 min read

Description

I just learnt about Rivest-Shamir-Aldeman, and so I created my own custom implementation. Here’s the message:

  n: 16537241065399537261146800802060451995107796665337288928060948677362154976656429797729550619497788311160926523026781503470362013597201944839389519773564618679827061417896265475971561610333659217333638238386907603525565178455941971399130722191602944445714002268747028340120907894781607422707823554701443768586256913491149809410232167277063066105859165079765281480076330718726350243973636606134346374770537701812923215229226027759112780757449828410180237267791126609342382918352166823253106960191346933601235547281
  e: 5
  ciphertext: [17623416832, 10510100501, 9509900499, 8587340257, 16105100000, 28153056843, 16850581551, 12166529024, 7737809375, 12762815625, 7737809375, 19254145824, 10510100501, 8587340257, 14693280768, 14693280768, 25937424601, 7737809375, 21003416576, 12166529024, 16850581551, 21924480357, 11592740743, 12166529024, 21003416576, 7737809375, 12762815625, 7737809375, 12166529024, 8587340257, 10000000000, 7737809375, 21003416576, 12166529024, 8587340257, 21003416576, 7737809375, 10000000000, 16850581551, 16105100000, 10510100501, 7737809375, 9509900499, 254803968, 19254145824, 19254145824, 345025251, 9509900499, 21003416576, 14693280768, 25937424601, 7737809375, 282475249, 282475249, 459165024, 312500000, 601692057, 30517578125]

Solution

RSA encryption works by calculating the equation encrypedMessage = message^(e) (mod N)

This makes two vulnerabilties in RSA, if e is so low that the mod N is not come into play, and if the two prime numbers that make up N are easily cracked.

With an e = 5, and an N of such size, it is likely that with just RSA, and no padding, which is believable to not have padding with how this was a custom implementation.

just creating some code, that does the fifth root of each character, and then converting to unicode with python:

N = 16537241065399537261146800802060451995107796665337288928060948677362154976656429797729550619497788311160926523026781503470362013597201944839389519773564618679827061417896265475971561610333659217333638238386907603525565178455941971399130722191602944445714002268747028340120907894781607422707823554701443768586256913491149809410232167277063066105859165079765281480076330718726350243973636606134346374770537701812923215229226027759112780757449828410180237267791126609342382918352166823253106960191346933601235547281
e = 5
Encrypted_Text = [17623416832, 10510100501, 9509900499, 8587340257, 16105100000, 28153056843, 16850581551, 12166529024, 7737809375, 12762815625, 7737809375, 19254145824, 10510100501, 8587340257, 14693280768, 14693280768, 25937424601, 7737809375, 21003416576, 12166529024, 16850581551, 21924480357, 11592740743, 12166529024, 21003416576, 7737809375, 12762815625, 7737809375, 12166529024, 8587340257, 10000000000, 7737809375, 21003416576, 12166529024, 8587340257, 21003416576, 7737809375, 10000000000, 16850581551, 16105100000, 10510100501, 7737809375, 9509900499, 254803968, 19254145824, 19254145824, 345025251, 9509900499, 21003416576, 14693280768, 25937424601, 7737809375, 282475249, 282475249, 459165024, 312500000, 601692057, 30517578125]


[print(chr(int(x ** (1/e))), end='') for x in Encrypted_Text]

In this code you need to watch out, as computers can’t do float math well, there is an error margin that makes the fifth root a float:

112.00000000000003,101.00000000000003,99.00000000000003,97.00000000000003,110.00000000000003,123.00000000000003,79.00000000000001,104.00000000000003,44.00000000000001,32.00000000000001,73.00000000000001,32.00000000000001,114.00000000000003,101.00000000000003,97.00000000000003,108.00000000000003,108.00000000000003,121.00000000000003,32.00000000000001,116.00000000000003,104.00000000000003,111.00000000000003,117.00000000000003,103.00000000000003,104.00000000000003,116.00000000000003,32.00000000000001,73.00000000000001,32.00000000000001,104.00000000000003,97.00000000000003,100.00000000000003,32.00000000000001,116.00000000000003,104.00000000000003,97.00000000000003,116.00000000000003,32.00000000000001,100.00000000000003,111.00000000000003,110.00000000000003,101.00000000000003,32.00000000000001,99.00000000000003,48.00000000000001,114.00000000000003,114.00000000000003,51.000000000000014,99.00000000000003,116.00000000000003,108.00000000000003,121.00000000000003,32.00000000000001,49.00000000000001,49.00000000000001,54.000000000000014,50.000000000000014,57.000000000000014,125.00000000000003

Running the python code gets you the flag pecan{oh_i_really_thought_i_had_that_done_c0rr3ctly_11629}

Back