Skip to content

Instantly share code, notes, and snippets.

@n-ari

n-ari/SweetLikeApplePie.md

Last active July 12, 2020 08:34
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save n-ari/f3caa913483ed5a7831ab04ff6fcef40 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save n-ari/f3caa913483ed5a7831ab04ff6fcef40 to your computer and use it in GitHub Desktop.
Download ZIP
Sweet like Apple Pie writeup
Raw
solve.cpp
#include <boost/multiprecision/gmp.hpp>
#include <iostream>
namespace mp = boost::multiprecision;
using mpf = mp::number<mp::gmp_float<300>>;
using Int = mp::mpz_int;
mpf calc_pi() {
mpf lasts = 0;
mpf t = 3;
mpf s = 3;
long long n = 1;
long long na = 0;
long long d = 0;
long long da = 24;
while (s != lasts) {
lasts = s;
n += na;
na += 8;
d += da;
da += 32;
t = (t * n) / d;
s += t;
}
return s;
}
const mpf pi = calc_pi();
const mpf enc =
mpf("0."
"1624524740929904080370625734082596882539951076434932935844265910039889"
"0346979100522213215889719862314493727953955534741355368819095990709595"
"2250683633029959235933436782707275021817801890433801800730214807785288"
"1122674466787471048875841910967491962127844701616702994954266797592216"
"52356130008110761143");
mpf sin(mpf x) {
// assert 0 <= x < pi
mpf p = 0;
mpf factor = x;
for (int n = 0; n < 10000; n++) {
p += factor;
factor *= -(x * x) / ((2 * n + 2) * (2 * n + 3));
}
return p;
}
template<typename T>
T modpow(T a, int b, T mod){
T r = 1;
while(b){
if(b&1)r=r*a%mod;
a=a*a%mod;
b>>=1;
}
return r;
}
const Int ten298 = mp::pow(Int(10),298);
Int calc(Int x, Int y, Int k=0, Int b=1){
// k * x == y mod 10^298
if( k * x % ten298 == y){
return k;
}
if(b >= ten298){
return 0;
}
Int nextb = b*10;
Int ylow = y%nextb;
for(int d=0; d<10; d++){
if(k*x%nextb == ylow){
Int ret = calc(x,y,k,nextb);
if(ret != 0)return ret;
}
k += b;
}
return 0;
}
int main() {
for(int cas=0; cas<2; cas++){
mpf low = cas ? pi : 0, high = pi / 2;
for (int _ = 0; _ < 1000; _++) {
mpf x = (low + high) / 2.0;
if (sin(x) <= enc) {
low = x;
} else {
high = x;
}
}
mpf md = low;
mpf ei = 9 - md;
Int enc, pii;
if(ei.str()[2] == '0'){
enc = Int(ei.str().substr(3,298));
}else{
enc = Int(ei.str().substr(2,299));
}
pii = Int(pi.str().substr(2,299));
for(int i=0; i<10; i++){
Int x = pii / 10;
Int y = enc / 10;
// find k s.t. k*pii == enc in decimal
Int k = calc(x, y+i);
if(k != 0){
std::cout << k.str() << "," << std::endl;
}
k = calc(x, y-i-1);
if(k != 0){
std::cout << k.str() << "," << std::endl;
}
}
}
return 0;
}
Raw
solve.py
from decimal import *
getcontext().prec = 300
def pi():
lasts, t, s, n, na, d, da = 0, Decimal(3), 3, 1, 0, 0, 24
while s != lasts:
lasts = s
n, na = n + na, na + 8
d, da = d + da, da + 32
t = (t * n) / d
s += t
return s
def sin(x):
x = Decimal(x) % pi()
p, factor = 0, x
for n in range(10000):
p += factor
factor *= - (x ** 2) / ((2 * n + 2) * (2 * n + 3))
return p
cand = [2499999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999916207340920592531211598362387906112675902047684168769266987543534671236411661117228597200143673839203030807459977105711293033466833950475117471144,
3038455549145276209102616162135598432317146487809537177067061055704919524499744526428531535233551951161284331003230025447015862520787234131888451924384290008556538977568785071584995398739604718196511546639582167947950457974518186765956499148353546841612495719833711411440404970524312114975624225627,
4461544450854723790897383837864401567682853512190462822932938944295080475500255473571468464766448048838715668996769974552984137479212765868111548075615542406125302207493638125139780413485747085898856790898951807139118884498305135468500695251933800836793565895086242799982181096409355785974610716661,
1076911098290552418205232324271196864634292975619074354134122111409839048999489052857063070467103902322568662006460050894031725041574468263776903848768663809772157362606358544807602891366533534345338924509897348352366244712624712414684401096563419844021960632207445717169516907581790279476130980110,
1423088901709447581794767675728803135365707024380925645865877888590160951000510947142936929532896097677431337993539949105968274958425531736223096151231168604909683822456064651917172920858818269750029413028636626734703097760198609819772793303723927834384100982712508494253069159351877621474103962178,
83792659079407468788401637612093887324097952315831230733012456465328763588338882771402799856326160796969192540022894288706966533166049524882528855,
3038455549145276209102616162135598432317146487809537177067061055704919524499744526428531535233551951161284331003230025447015862520787234131888451924384457593874697792506361874860219586514252914101143209101048192860881115501694864531499304748066199163206434104913757200017818903590644214025389283338,
4461544450854723790897383837864401567682853512190462822932938944295080475500255473571468464766448048838715668996769974552984137479212765868111548075615709991443461022431214928415004601260395281803488453360417832052049542025481813234043500851646453158387504280166288588559595029475687885024375774372,
1076911098290552418205232324271196864634292975619074354134122111409839048999489052857063070467103902322568662006460050894031725041574468263776903848768831395090316177543935348082827079141181730249970586971363373265296902239801390180227206696276072165615899017287491505746930840648122378525896037821,
1423088901709447581794767675728803135365707024380925645865877888590160951000510947142936929532896097677431337993539949105968274958425531736223096151231336190227842637393641455192397108633466465654661075490102651647633755287375287585315598903436580155978039367792554282830483092418209720523869019889]
pipi = pi()
enc = Decimal("0.162452474092990408037062573408259688253995107643493293584426591003988903469791005222132158897198623144937279539555347413553688190959907095952250683633029959235933436782707275021817801890433801800730214807785288112267446678747104887584191096749196212784470161670299495426679759221652356130008110761143")
for k in cand:
flag = enc + k*pipi
# if (flag % 1) > 0.01:
# continue
flag = str(flag)
while flag[-1] != '.':
flag = flag[0:-1]
flag = flag[0:-1]
flag = int(flag)
# if flag > 2**500:
# continue
print(flag)
hx = hex(flag)[2:]
if len(hx) % 2 == 1:
hx = '0' + hx
print(hx)
print(bytes.fromhex(hx))
Raw
SweetLikeApplePie.md

Sweet Like Apple Pie

The output is output = sin(flag % pi()).

We can get flag % pi() = arcsin(output) using a binary search. Note that there are 2 possible answers.

So, we want to calculate k such that flag - k * pi() = arcsin(output).

Due to the Decimal, these values are calculated in 300-digits precision. That means,

pi          =           3.1415...4120
k           = xxxx...xxxx
k * pi      = wwww...wwww.wwww...wwww
flag        = yyyy...yyyy
flag - k*pi = zzzz...zzzz.zzzz...zzzz = arcsin(output)

To get correct k, determine from least-significant-digit to most-significant-digit of k so that the lower digits of arcsin(output) + k * pi will all be zero. This can be done in integers.

Considering 2 outputs of arcsin and some noise in arcsin, we get some candidates of k, and get a flag.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment