Tags: euler totient-function python chinese-remainder math
Rating:
# misc04 (misc / PPC, 36 solved, 140 points)
###### Author: [ecurve](https://github.com/Pascalao)
We solved this challenge outside the time of the CTF competition.
And we saw the hint also to late =)
```
nc misc04.grandprix.whitehatvn.com 1337
Hint:
After get the message "It's a friendly point", you should send the friendly point value.
```
The first step was to connect with `nc` to the server.
And we get the following output:
```
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: 7347393
Face Lip point Nose point Eyes point Forehead point
:-) 41863631 100490338 433902094 652873459
(';') 720650625 719706929 44632477 56144347
(=^..^=) 142081259 704875476 699749648 315470258
:) 294722291 970850134 450232131 742462129
:-] 226920560 95009694 122204027 45544752
:] 419978636 168795806 749824651 172388267
:-3 169061389 163458935 230239302 833499806
:3 222659915 376053203 884875332 926897367
:-> 512342718 430836314 883613002 162365796
:> 973214807 983055326 618589886 458617752
:-* 829485678 183173013 866762490 760677473
:* 911863323 750034484 911025469 282700283
(>_<) 804361569 70671270 237648402 386389863
(>_<)> 717041150 784422762 230679235 697209215
(';') 870541725 934604474 324535939 136986572
(^_^;) 321876650 34072193 145777397 852149094
(-_-;) 262428332 256022776 360070021 65638453
(~_~;) 40608999 564673488 680170138 698406302
(...;) 253840701 631934411 476435244 374214943
(._.;) 700299153 981981513 7044560 574931063
^_^; 544644229 860203042 822713284 552102413
(#^.^#) 600326407 882227414 388105971 763458706
(^^;) 373505617 52212685 283729546 357811738
(-_-)zzz 256558496 697339357 432211055 257217653
(^_-) 986605960 827562811 301786730 477861902
((+_+)) 881187058 65057223 24659124 213451687
(+o+) 275497163 288736614 50199023 268649149
^_^ 538051279 285360765 121867499 424071406
(^_^)/ 707023019 713830152 667400168 136843612
(=_=) 47051104 163496837 931430998 823383842
(?_?) 27892640 489730114 115638092 926684657
(^_^) 706239741 996099289 249987426 169742952
(~o~) 250868895 563094797 49935015 577994314
(~_~) 54032798 925798112 899056668 127589356
o.O 682485064 980406575 651792259 87240399
(o.o) 725167086 225426937 282593914 621300845
oO 695254837 70651574 624587926 707196405
<_< 388528103 868067275 179985006 267407499
>_> 673388376 207088819 549401573 659942714
<o?o> 465291384 340604990 248740621 45935548
(>^.^) 948038027 61723675 712394516 985751951
(^.^<) 567177368 22673350 92544178 771356741
>,< 832402970 734202391 756116941 46767329
;-( 374064070 30600765 462618136 63339419
>:-( 382441003 606198478 890713495 940274731
@(-_-)@ 189071406 295840184 922086980 635274564
@(^_^)@ 898771760 569141358 483359747 771645465
~O-O~ 867059109 379549606 804780338 498400529
:)] 353115702 413932035 27502013 488912767
.-] 662536162 428534547 99691553 559342638
.-) 567420268 254121739 759892191 902206113
,-) 211722291 211055745 40153010 943548463
':-( 703059585 264763832 559452046 795390806
'-) 445344877 641959889 447832553 230293274
:-D 302439952 149525107 248658785 590936387
:=) 71320926 440537376 225390230 405834011
:@ 471240984 401395194 650316707 121250193
<:-P 885828844 757049808 177839767 163444877
:)>- 588861568 622206413 432416797 691027975
:^) 624429541 463900092 915196501 279579098
3:] 461450342 489729205 736810229 876391148
(o^-^o) 603717335 40046406 890661588 885059023
:-< 428998319 776556312 925447901 911898860
:-[ 361537285 904944936 715276147 272664518
=:-) 35275637 575675666 583156390 300641006
:-)) 161441970 337852758 663729734 39086149
<(-_-)> 698163763 27838325 386413007 523042449
9_9 657113673 493452343 984091980 561393575
=)) 618619426 98516825 787280863 523374517
7:) 65306089 263773625 195414947 38285294
(<_>) 251305509 931217756 763095170 785205173
:-( 317188517 199999679 283049770 139941061
/:-) 794219931 103013193 689585453 82085845
(-_-) 588012907 136457816 64740029 385913950
:-* 885842581 911584499 747602027 638103907
::=)) 470637566 213120890 471126462 619593967
o_o 60587976 397232681 71622142 668785916
(*^_^*) 411865834 627167204 223220937 280693125
(-::-) 5201502 825489382 463059357 999510308
(^o^) 594623613 663272956 613938262 485372758
:o) 507608626 737864929 20847000 741437727
:|) 433567323 487050957 866942897 165446081
:) 864253778 818516831 501103983 712336363
:-) 899189427 295206846 139726367 911551791
+:-) 176684993 593281940 406054423 394271269
(:-) 942438571 760000844 121984677 791970681
{:-) 443888692 255299521 987711685 178432709
^&^ 311639969 981312694 890393090 73653885
=.= 593892241 520092250 615590736 107109331
*~* 833482387 908375855 152209426 104232647
(:>-< 190398687 742557605 453762505 409580622
:-)--- 7829689 28416414 946899780 331887275
*-) 928156226 968281617 822076531 910024798
>:* 595073743 58819761 922885299 20966126
>.< 799588936 72213296 288322962 186934867
:-@ 857756440 93121103 870486185 986562930
(:)-) 262026515 583862942 848985028 867245954
::-) 215692113 568497630 106532166 103073639
:-@ 632932254 818049989 596094296 275422582
@,.,@ 633390760 151902998 636327201 992469562
:-E 737765183 155845512 684251823 461953438
:-[ 560366934 823304271 158732341 394302375
:-)) 747840673 449190960 683246169 138021176
:-[] 109466704 331984671 775806357 128282672
:-))) 622198647 160262735 403905751 155644881
(:- 51814229 867666068 570607084 496475649
$_$ 963994883 264719832 533053302 722484950
(^:^) 831440495 622948710 932932521 493860350
|___| 268505836 775285424 933064452 981412480
:-) 316352295 694512575 342932333 191921001
>O< 614805177 725818288 230941984 147277283
:=) 418610190 985008589 967876841 699547535
-:-) 903170462 399878523 469616931 472889643
|:-) 410902296 132464699 751647940 382987300
<(^.^<) 582581909 999713141 191927660 557712276
<(*.*<) 571232294 670303488 341903736 602512313
(*_*) 349216258 690159136 143329853 58677017
._. 731037377 843548606 226650296 962637137
@:-) 179816022 867927252 600277313 522069197
<('.')> 605328171 925414409 337872721 858718991
<('.'<) 910045319 212091881 259368181 599648462
<(^.^)> 410545168 806701810 605362681 821719551
<('.'<) 762367016 382642244 296311819 969809800
:-* 210854564 118702731 998475147 620871185
(:-* 965125934 177277283 648124772 445552689
=^.^= 333364710 757923083 970697210 28024835
<{::}> 426744479 299838105 72300327 84046263
:-D 341392777 331707403 318580407 874598364
:)) 85325256 163018313 958811451 362164312
:.-) 62974551 445278119 976956569 762984433
(-: 420535558 171164063 33207427 514530228
>;-> 332030262 652369549 491257133 627112751
:^o 886223895 283538264 265213843 725705006
:-9 355571176 913389899 422264175 842899119
So, what is the most friendly face?
```
Ok, cool! We have to compute the formula
```
(lip point**nose point)**(eyes point**forehead point) mod Face_index
```
But we know that the formula is heavy to compute, because of the much exponentiation and the big integers.
Ok, how we can transpose this formula to compute the friendliness value really fast?
After hours of researching, we found a question on [stackoverflow](https://stackoverflow.com/questions/4223313/finding-abc-mod-m),
how it is possible to compute such values faster.
Before we found that, we thought on the eulers theorem, but we did not found a real solution for it.
But with that question on stackoverflow it was clear, how we can compute it.
We used the python function from an answer of that question to compute the friendliness values.
The functions are available on [ideone.com](https://ideone.com/bOxFqJ)
Now we can compute all the friendliness values of the emojis and append it to a list.
After them we sort them and take the first emoji and his value from that list.
We send the solution to the server and that for every stage.
We reached the stage 5 and solved that.
After them we get the flag:
```
Congrats! Flag, flag, flag!: WhiteHat{^.^_M4th_Math_Chin3se_Rema1nder_The0rem_&_Euler's_ThEorem_M@th_MAth_^/^}
```
To solve that it is good to know the euleurs theorem and chinese remainder theorem.
