In this challenge we are presented with a remote service asking us a question:

Here we use a well-known cryptosystem, which introduced in late 90s as a part of PhD Thesis. This cryptosystem is a probabilistic asymmetric algorithm, so computer nerds are familiar with the basics. The power of this cryptosystem is based on the fact that no efficient general method for computing discrete logarithms on conventional computers is known. In real world it could be used in a situation where there is a need for anonymity and a mechanism to validate, like election. What’s the name of this cryptosystem?

After some googling we found that the answer is “Paillier”, later we receive this prompt:

The secret is:

642807145082286247713777999837639377481387351058282123170326710069313488038832353876780566208105600079151229044887906676902907027064003780445277944626862081731861220016415929268942783162708816500946772808327134830134079094377390069335173892453677535279678315885291394526580800235039893009001625481049390361761336337647597773237774304907266052473708273977012064983893047728185071148350402161227727584760493541436392061714945686426966193498593237383322044894184438689354989491800002299012669235551727100161976426628760839759603818593410342738847167887121724862806632881028892880165650108111619269651597119870237519410
Tell us your choise:
------------------------
[E]ncrypt: [D]ecrypt:

So we have an oracle for encryption and decryption, unfortunately there are some restrictions:

  • We cannot ask for decryption of the secret (of course)
  • We cannot encrypt or decrypt large messages

If we read the Wikipedia page about the Paillier cryptosystem we will notice something interesting: its homomorphic properties! In fact D(E(m1) * E(m2) mod n^2) == m1 + m2. So the main idea is the following:

  1. Ask for encryption of, let’s say, 1
  2. Compute secret * E(1) and ask for its decryption
  3. Compute the result - 1, convert to hex and interpret as ASCII and get the flag

Unfortunately we cannot ask for decryption of large messages, and secret * E(1) will be too large! We would need the modulus N, so we can compute (secret * E(1)) mod n^2 and have an equivalent smaller value. But how to get N? As every message to encrypt needs to be < N we can use binary search by sending different messages until we reach N.

Here’s a script to achieve this.

Once we get the modulus we can proceed with the method explained above and decode the secret.

Example with

N=28414252178421170251910042147689368446511995764529924640302525001150082023847807850723344018358163485930344707394699713532305322202216635189806057491940857063203918400016948903778913790645080815377317956510275921513980400357522675326929234601338948461475089468134681894547897715946279673410647104276477333937

[E]ncrypt: [D]ecrypt: E
Tell us your message to encrypt: 1
Your secret is:
10254271016252210195542853917473787208480697441500992362070509363446634302492480614016623460575247351704302092065572900756142657693931498644296908286370447239861288216597760672629661168916522831223423485175487208158956410129340462987845165959364044531123268749519229555452011722246206484826475478883916666045408936682867713580546776560013587005204855238017289992567196239961440988327284647272451217326272341334087605709592271109729248228970719188943236112512862438403670090398469049945737686554001310377359723720459889274699951458658754306914949330451700742984310780806842004029938307302048470547437887140646430919

Tell us your choise:
------------------------
[E]ncrypt: [D]ecrypt: D
Tell us your secret to decrypt:
378869925736130699327946615429907070640619801721442952176981309580079338156777297429171610327509248652989924893645641377825963429879984272216416464476321235806362871805661286277910203750425312658493525312323997215491078386668980228200854933609165456659525647589450141093860116755196997077301046890511770283350924340428804296597920442693534639593512760942167807001656749830526760236308753395339093165903779626130884818462654376226323253879824356656487323415435290569523516396412801068709493337073377378335398783991338155822741273015720465422092438527443228035014323257907192901437355493348024470184769657927580423795
Your original message is:
32487808320243150435316584796155571093777738593139558163862909500838275925645449950017590

>>> hex(32487808320243150435316584796155571093777738593139558163862909500838275925645449950017590)[2:-1].decode('hex')

'ASIS_85c9febd4c15950ab1f19a6bd7a94f86'

fox & immerse