Skip to content
Branch: master
Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
README.md

README.md

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:

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_^/^}

You can’t perform that action at this time.