Tags: euler modpow
Rating:
# Misc 04 (misc, 140p, 36 solved)
In the task we get access to an application:
```
Wellcom to Friendly face challenge
According to experts, the formula for measuring the friendliness of a face is
(lip point**nose point)**(eyes point**forehead point) mod Face_index
Now play!
------------------------------Stage 1--------------------------------------
Face_index: 9928546
Face Lip point Nose point Eyes point Forehead point
:-) 568824892 457742011 941012180 253144504
(';') 23952035 628931911 972045092 777026341
(=^..^=) 686029537 64319452 611190375 112129192
:) 617374078 81959857 20649197 24703650
:-] 280039606 627778866 988980689 684158291
:] 60783119 594342583 347303300 539141757
:-3 321261378 928676123 34262697 822086619
:3 321223152 802095261 306245331 746806683
:-> 267149366 274650373 453784293 155962876
:> 147037766 878265535 332179064 544535138
:-* 282364953 414082899 798987403 764105746
:* 583265502 889346653 407539632 137243339
(>_<) 133984875 66646715 716020719 488324317
(>_<)> 727687008 366192925 114776444 54859934
(';') 437962554 268054657 936090419 377085453
(^_^;) 964356686 583217140 860994507 930144447
(-_-;) 574103967 483119825 355139943 678768494
(~_~;) 389800758 803218695 435535853 239965696
(...;) 359662407 610432925 642837810 772797892
(._.;) 509720900 307969711 80913034 958275474
^_^; 859083357 536473752 783709719 414574837
(#^.^#) 557456218 753671213 649539972 266160251
(^^;) 140043688 782606707 915951984 913136529
(-_-)zzz 866318536 905466702 220292777 185393572
(^_-) 445063898 96616021 982269754 18154
((+_+)) 792421359 230028929 670678620 542664022
(+o+) 902780243 773999795 696449166 573196057
^_^ 482459943 486150568 797684171 883635208
(^_^)/ 194918846 505240052 344925190 628519414
(=_=) 204409002 470486904 847693668 200782527
(?_?) 641072342 281225817 293240755 321003907
(^_^) 324078528 889045681 483983051 103283684
(~o~) 57590473 618155926 389926985 4295912
(~_~) 480720695 535339640 709805607 130080855
o.O 88139622 584724341 528917361 868022901
(o.o) 31773824 321278395 230937564 139287394
oO 929305518 457021266 885282508 821646046
<_< 483063468 713769808 6404138 983646898
>_> 86259272 495387210 523761674 655522004
<o?o> 352569223 806985052 405453886 96888458
(>^.^) 13446885 781237903 842345802 967302054
(^.^<) 155704256 872607202 492051377 40621810
>,< 589494855 375474890 12910056 55721531
;-( 445793591 485056031 42055133 264070003
>:-( 273791760 575559835 149683227 202477348
@(-_-)@ 385413303 476361140 733303627 988872984
@(^_^)@ 162219164 322345611 136067195 835475504
~O-O~ 871128442 534455323 132275419 372845099
:)] 789516425 636339074 530573592 89693503
.-] 720189903 767600763 32801237 62540911
.-) 526402082 503564697 735408367 406646597
,-) 284230473 377456495 171934951 584351302
':-( 934728851 411860493 740283917 152086679
'-) 296992354 721230115 853558354 582693347
:-D 611619258 364242222 775590048 18022636
:=) 149406960 655734808 401841140 420418918
:@ 524904631 323701516 445590058 166023135
<:-P 90295722 328295842 900424357 455755334
:)>- 860279369 879340025 531178009 275273365
:^) 998244997 568869594 564026954 915507847
3:] 627467503 261246151 519795303 424916420
(o^-^o) 127803732 820062459 77131195 633921273
:-< 503659779 716296684 790584903 993366886
:-[ 596497706 233554771 660617582 380800144
=:-) 330896284 451246310 901770941 803795916
:-)) 722082675 530353406 720006166 914873545
<(-_-)> 436096951 167519805 895912006 597810060
9_9 182635947 968356305 365764220 374100297
=)) 357705508 909193878 176866598 126632317
7:) 52189358 812712480 882190330 90405608
(<_>) 992091929 126117984 520145161 784652516
:-( 958493227 371815292 156487035 318488198
/:-) 798055879 768101151 854110711 293863015
(-_-) 247572818 96884158 225496762 524371879
:-* 476938541 184608385 859713180 38362037
::=)) 217212770 475918153 8001010 52368247
o_o 960321847 777557966 370232776 603559555
(*^_^*) 164917508 497580071 304718977 778749984
(-::-) 135600425 591552662 411230811 844033074
(^o^) 114043599 267851809 764197233 729657426
:o) 77033635 724309071 532256499 650125580
:|) 92133304 673460316 661186700 844697945
:) 341143663 291599585 224605429 514213089
:-) 616261301 602862592 150890219 603786555
+:-) 413093363 228415667 18326665 17079145
(:-) 584187072 634395735 223113532 45382578
{:-) 343750287 1908872 702997957 311091423
^&^ 529079589 574938394 233399359 117832407
=.= 577014898 409511688 354573727 22364817
*~* 196610398 165376804 497915681 485447329
(:>-< 804706985 474755647 535797022 259962366
:-)--- 860526346 688746022 263287692 724472915
*-) 221928355 887834546 690209569 140649690
>:* 707429706 361667628 890981899 628576789
>.< 478256657 679452160 427569933 398252856
:-@ 842685569 29408161 399813077 195286593
(:)-) 113217668 630504653 722567738 220013519
::-) 628424516 717349638 437425785 947963941
:-@ 200636705 54273079 500779926 631110356
@,.,@ 825607979 674708189 134882532 860611414
:-E 817325600 356562506 392950183 347761068
:-[ 390102746 649147663 973292798 37327144
:-)) 915390296 615745566 588286121 438513696
:-[] 350818957 706941720 99500462 444421129
:-))) 624037961 151807502 848569245 7192210
(:- 406777048 375986160 967616861 522557149
$_$ 153721779 510099055 549303633 537910630
(^:^) 382883033 599595304 18464969 317011415
|___| 450066663 771458013 361548329 929201245
:-) 988605304 120169270 719780182 198013944
>O< 62694268 154947217 61736412 370202519
:=) 139611307 27068908 347349262 802145594
-:-) 711270769 958899932 320121022 25695782
|:-) 902903753 847237435 370638588 515861385
<(^.^<) 36414441 29167376 972164958 643757408
<(*.*<) 44726993 507681673 93259730 375999094
(*_*) 660115130 36934065 950811076 706589789
._. 656708457 60027297 874367948 436077729
@:-) 904147006 657729620 590037586 614605662
<('.')> 22338651 744151297 421884827 680423420
<('.'<) 915666254 755172274 357152642 71468540
<(^.^)> 761583139 274093669 579566114 968424306
<('.'<) 1846023 999575088 416255614 542189089
:-* 61411542 934130467 317698883 862889327
(:-* 538367672 206718285 784199878 929721277
=^.^= 38191813 444179562 50803550 607621511
<{::}> 762261539 665199139 29749796 589314027
:-D 813417897 516749674 198678296 492384881
:)) 692507260 933243641 910076492 177113479
:.-) 706350257 208220064 561827765 973675855
(-: 460728977 389190842 848053504 746993263
>;-> 2871890 469626441 251807800 158741716
:^o 861438792 24236048 616330095 273007266
:-9 959789499 631364945 414035584 939194517
So, what is the most friendly face?
```
It's quite clear what we need to do: calculate `(lip point**nose point)**(eyes point**forehead point) mod Face_index` for each of the emojis and then send back to the server the one with highest score.
First optimization we can do is trivial, and comes directly from modular arithmetics:
`(a**b) mod n = ((a mod n)**b) mod n`
And of course `pow(a,b,n)` is much faster than `a**b` to calculate.
The real struggle is the second part - how to optimize calculation of `b`.
After a while we came up with an idea, that if certain conditions were met, we could actually use Euler theorem here.
Euler theorem says that if `a` and `n` are `co-prime` then `a**phi(n) mod n = 1`.
This is useful, because `1**x` is always 1.
This would mean, that we could simplify our `b` to `b mod phi(n)`.
For example we want to calculate `7**222 mod 10`:
1. `phi(10) = (2-1)*(5-1) = 4`
2. `7**222 mod 10 = 7**(4*55) * 7**2 mod 10 = (7**4 mod 10)**55 * 7**2 mod 10 = 1**55 * 7**2 mod 10 = 7**2 mod 10`
3. We could also simply notice that `222 mod 4 = 2` and thus `7**222 mod 10 = 7**2 mod 10`
We can apply the same logic here, and re-write the equation:
```
(lip point**nose point) = a
(eyes point**forehead point) = b
Face_index = n
(lip point**nose point)**(eyes point**forehead point) mod Face_index = a**b mod n
a**b mod n = (a mod n)**b mod n
a**b mod n = a**(b mod phi(n)) mod n
a**b mod n = (a mod n)**(b mod phi(n)) mod n = pow(a%n, b%phi(n), n)
a**b mod n = pow(pow(lip point, nose point, Face_index), pow(eyes point, forehead point, phi(Face_index)), mod Face_index)`
```
Keep in mind, this is all true only if `a` and `n` are `co-prime`, but we simply assumned they would be.
Solver written in python is:
```python
import re
from crypto_commons.generic import factor
from crypto_commons.netcat.netcat_commons import nc, receive_until_match, send
from crypto_commons.rsa.rsa_commons import get_fi_repeated_prime
def main():
s = nc("misc04.grandprix.whitehatvn.com", 1337)
while True:
data = receive_until_match(s, "So, what is the most friendly face\?", 5.0)
print(data)
modulus = int(re.findall("Face_index: (\d+)", data)[0])
primes = factor(modulus)[0]
phi = 1
for prime in set(primes):
k = primes.count(prime)
phi *= get_fi_repeated_prime(prime, k)
max = (0, "")
for dataset in re.findall("(.*?)\s+(\d+)\s+(\d+)\s+(\d+)\s+(\d+)", data):
face, lip, nose, eye, fore = dataset
a = pow(int(lip), int(nose), modulus)
b = pow(int(eye), int(fore), phi)
result = pow(a, b, modulus)
if result > max[0]:
max = (result, face)
print("sending", max)
send(s, max[1])
send(s, str(max[0]))
pass
main()
```
Which gives us: `WhiteHat{^.^_M4th_Math_Chin3se_Rema1nder_The0rem_&_Euler's_ThEorem_M@th_MAth_^/^}`
