Skip to content

Instantly share code, notes, and snippets.

Notice that $(ap + bq)^e = \binom{e}{0} (ap)^0 (bq)^e + \binom{e}{1} (ap)^1 (bq)^{e-1} + \ldots + \binom{e}{e-1} (ap)^{e-1} (bq)^1 + \binom{e}{e} (ap)^e (bq)^0$ by the Binomial Theorem, so all terms cancel out except for the first and last one similarly to the Freshman's Dream (although in this case the terms in the binomial are doing the canceling, not the binomial coefficients as in the Freshman's Dream theorem).

So $c_1 = (2p)^{e_1} + (3q)^{e_1} \pmod{N}$, and this applies similarly for $c_2$.

Now we can't directly combine the equations because they have different exponents on the terms. However, we can raise $c_1$ to the power of $e_2$ and vice versa to make the exponents on both equations $e_1e_2$.

Then, we can simply multiply $c_1$ by a modular inverse so that the coefficients of the $q$ terms in $c_1$ and $c_2$ are the same and then subtract and use another inverse to get $p^{e_1e_2}$.

Finally, since $p$ is present in both $p^{e_1e_2} \pmod{N}$ and $N = pq$ and the exponent of $p$ in $N$ is just $

First, notice that the value $a$ is a quadratic residue which can be confirmed with Euler's Criterion (another hint comes from the title which references Adrien-Marie Legendre). The encryption script raises $a$ to a random exponent $e$, but $a^e$ will still be a quadratic residue. However, if the bit is $0$, then it gets negated. $p \equiv 3 \pmod{4}$, so $-1$ is not a quadratic residue; therefore, by the laws of quadratic reciprocity, the resulting residue will not be a quadratic residue (since a non residue times a residue is a non-residue). So a value in the resulting array corresponds to a $1$ bit iff it's a quadratic residue. From here it's pretty easy to write a decryption script:

ct = [67594220461269, 501237540280788, 718316769824518, 296304224247167, 48290626940198, 30829701196032, 521453693392074, 840985324383794, 770420008897119, 745131486581197, 729163531979577, 334563813238599, 289746215495432, 538664937794468, 894085795317163, 983410189487558, 863330928724430, 996272871140947, 3521752

Keybase proof

I hereby claim:

  • I am programmeruser2 on github.
  • I am programmeruser ( on keybase.
  • I have a public key whose fingerprint is D0A2 524A B9AE DA1B A4DB DC08 7C6D 52D0 088C 9AFB

To claim this, I am signing this object:

// Run on ShaderToy
void mainImage(out vec4 fragColor, in vec2 fragCoord) {
fragColor = vec4(distance(fragCoord, iResolution.xy/2.0)/(sqrt(iResolution.x*iResolution.x + iResolution.y*iResolution.y)/2.0), 0.0, 1.0, 1.0);
#include <stdio.h>
int main(void) {
printf("size=%d", sizeof(int));
This file has been truncated, but you can view the full file.
Tàu Hiĕk
Bàng-uâ kō̤-nèng sê:
const iframe = document.getElementById('iframe'); //OR WHATEVER
// create a document and pipe to a blob
var doc = new PDFDocument();
var stream = doc.pipe(blobStream());
const cards = data.split('\n');
const allPages = [];
cards.forEach(card => {
const [a,b] = card.split('\t');
export DISPLAY=$(powershell.exe -Command '(Get-NetIPAddress -AddressFamily IPv4 | Where-Object {$_.AddressState -eq "Preferred" -and ($_.InterfaceAlias -eq "Wi-Fi" -or $_.InterfaceAlias -eq "Ethernet")}).IPAddress' | sed 's/.$//'):0.0
programmeruser2 / jwt.js
Last active May 31, 2022 09:15
Decode JWT
const decodeJwt = token => token.split('.').map((item,index) => index==2?item:JSON.parse(atob(item)));
const encodeJwt = segments =>,index)=>index==2?item:btoa(JSON.stringify(item))).join('.');
programmeruser2 / ip.ps1
Last active July 5, 2021 13:52
Get the Wi-Fi or Ethernet IP Address
(Get-NetIPAddress -AddressFamily IPv4 | Where-Object {$_.AddressState -eq "Preferred" -and ($_.InterfaceAlias -eq "Wi-Fi" -or $_.InterfaceAlias -eq "Ethernet")}).IPAddress