# Misc 04 (misc, 140p, 36 solved)
In the task we get access to an application:
```                   Wellcom to Friendly face challengeAccording 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: 9928546Face           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) = bFace_index = n
(lip point**nose point)**(eyes point**forehead point) mod Face_index = a**b mod na**b mod n = (a mod n)**b mod na**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:
```pythonimport re
from crypto_commons.generic import factorfrom crypto_commons.netcat.netcat_commons import nc, receive_until_match, sendfrom 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_^/^}`