GXYCTF2019-CommonModulusAttack

此为BUU上的一道题。

---

分析一下各函数功能

oldtest():产生20个随机数，写入old.txt中
generate_init_state(): 功能易懂，但字太多不写了。
gen_states():生成p,q,n,加密m，将n写入product中，c写入states
encrypt():CBC加密
gen_new_states():将states的前24个数据按顺序进行CBC加密，写入states，同时stateselse += 24
stateconvert():返回CBC加密后的结果
lrandout():stateselse>0时，按顺序取states中的数据并进行CBC加密;stateselse<0时，先gen_new_states()
再取数据
byte2hex():顾名思义，字节转16进制
convert_2_binary():字节转2进制
initseed():flag做初始seed

整体过程为，首先是一键三连（oldtest()、initseed()、gen_states()），然后循环24次lrandout()，此时stateselse=0,statespoint=24，会进行依次gen_new_states()，然后再次进行24次lrandout()，写入new.txt中的数据依次是$E_{CBC}(E_{CBC}(RSA_{0}))$~$E_{CBC}(E_{CBC}(RSA_{23}))$，也就是state[:24]进行了两次CBC加密。

解题关键在于破解CBC的密钥，这可能需要预测随机数，查询得知java.util.Random.nextInt()使用的是线性同余发生器LCG。java使用的参数和方程如下：

a = 25214903917, b = 11, m = 281474976710655
seed = (a*seed + b) & m

（附上某书的相关图片）

爆破seed过程如下：

private static long a = 0x5deece66dL;
private static long b = 11L;
private static long m = 0xffffffffffffL;
public long crack_seed(long out1, long out2) throws Exception {
    for (int i = 0; i <= 0xffff; i++) {
        long seed = (out1 << 16) + i;
        long guess_out2 = (a * seed + b & m) >>> 16;
        if (guess_out2 == out2) {
            System.out.println("[+] PRNG's seed: " + String.valueOf(seed));
            return seed;
        }
    }
    throw new Exception("[!] PRNG crack failed!");
}

得到seed之后，就可以预测AES/CBC的密钥key，以及RSA的p,q，需要注意的是顺序和次数的问题

• 首先过滤old.txt产生的随机数共计19次
• 然后生成RSA的p,q共计24次
• 最后是AES/CBC共72次，前24次的随机数对解题无用，中间24次的随机数是$E_{CBC}(RSA_c)$的密钥key1，最后24次是$E_{CBC}(E_{CBC}(RSA_{c}))$的密钥key2。需要注意若将随机数直接存入文件再读取，长度不够16bit，需要进行byte2hex()。

java代码如下：

import java.io.IOException;
import java.io.*;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Random;
import java.lang.*;
import java.util.Arrays;
class crak_into_RSA {
    
    Random random = new Random();
    private static long a = 0x5deece66dL;
    private static long b = 11L;
    private static long m = 0xffffffffffffL;
    //爆破种子
    public long crack_seed(long out1, long out2) throws Exception {
        for (int i = 0; i <= 0xffff; i++) {
            long seed = (out1 << 16) + i;
            long guess_out2 = (a * seed + b & m) >>> 16;
            if (guess_out2 == out2) {
                System.out.println("[+] PRNG's seed: " + String.valueOf(seed));
                return seed;
            }
        }
        throw new Exception("[!] PRNG crack failed!");
    }
	//设置种子
    public void SetSeed(long seed){
        this.random.setSeed(seed ^ a);
    }
	//读文件
    public ArrayList<Long> ReadFile(String fileName) {
        ArrayList<Long> states = new ArrayList(24);
        File file = new File(fileName);
        BufferedReader reader = null;
        try {
            reader = new BufferedReader(new FileReader(file));
            String tempString = null;
            while ((tempString = reader.readLine()) != null) {
                states.add(Long.valueOf(tempString));
            }
            reader.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return states;
    }
	//过滤前24个随机数
    public void oldtest(){
//        ArrayList<Integer> old = new ArrayList<Integer>();
        for(int i=0;i<19;i++){
            int tmp = this.random.nextInt();
//            old.add(tmp);
        }
    }
	//利用随机数发生器产生RSA的p,q
    public void gen_RSA(){
        BigInteger var2 = BigInteger.valueOf(17L);
        ArrayList var3 = new ArrayList(24);
        ArrayList var4 = new ArrayList(24);

        for(int var5 = 0; var5 < 24; ++var5) {
            BigInteger var6 = BigInteger.probablePrime(512, this.random);
            BigInteger var7 = BigInteger.probablePrime(512, this.random);

            var3.add(var6);
            var3.add(var7);
        }

        try {
            PrintWriter var11 = new PrintWriter("p_and_q", "UTF-8");
            for(int var12 = 0; var12 < 24*2; ++var12) {
                var11.println(((BigInteger)var3.get(var12)).toString());
            }
            var11.close();
        } catch (IOException var10) {
            var10.printStackTrace();
        }
    }
	
    public static String byte2hex(byte[] var0) {
        StringBuffer var1 = new StringBuffer(var0.length * 2);

        for(int var2 = 0; var2 < var0.length; ++var2) {
            if ((var0[var2] & 255) < 16) {
                var1.append("0");
            }

            var1.append(Long.toString((long)(var0[var2] & 255), 16));
        }

        return var1.toString();
    }
	//利用随机数发生器产生AES/CBC的key
    public void gen_CBC_key(){

        //24次无用
        for(int i=0;i<24;i++){
            byte[] var3 = new byte[16];
            this.random.nextBytes(var3);
        }

        ArrayList var4 = new ArrayList(48);
        for(int i=0;i<48;i++){
            byte[] var3 = new byte[16];
            this.random.nextBytes(var3);
            var4.add(byte2hex(var3));
        }

        try {
            PrintWriter var11 = new PrintWriter("CBC_key", "UTF-8");
            for(int var12 = 0; var12 < 48; ++var12) {
                var11.println(var4.get(var12));
            }
            var11.close();
        } catch (IOException var10) {
            var10.printStackTrace();
        }
    }

    public static void main(String[] args) {
        crak_into_RSA obj = new crak_into_RSA();
        ArrayList<Long> old = obj.ReadFile("old.txt");
        System.out.println(old);
        long seed;
        try {
            seed = obj.crack_seed(old.get(0), old.get(1));
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
        obj.SetSeed(seed);
        obj.oldtest();

        obj.gen_RSA();
        obj.gen_CBC_key();

    }

}

(我承认我java很菜，不喜欢用java，类型转换都够呛的)

接下来就是利用得到的密钥key（IV向量根据代码可知为空，即全0）以及p,q解密得到generate_init_state()之后的c，要想进一步得到flag只需要不断重复generate_init_state()。（话说这周期性是怎么看出来的）

python代码如下：

from randcrack import RandCrack
from Crypto.Util.number import *
from Crypto.Cipher import AES
from gmpy2 import *
from binascii import unhexlify

def dec_CBC(key,eenc):
    key1, key2 = key[:24], key[24:]
    rsac = []
    for i in range(24):
        aes1 = AES.new(key1[i], AES.MODE_CBC, iv=b'\x00' * 16)
        aes2 = AES.new(key2[i], AES.MODE_CBC, iv=b'\x00' * 16)
        enc = aes2.decrypt(eenc[i])
        rsac.append(bytes_to_long(aes1.decrypt(enc)))

    return rsac

def ReadFile():
    modulus = []
    with open(r'product','r') as f:
        txt = f.readlines()
        for line in txt:
            modulus.append(int(line))

    key = []
    with open(r'CBC_key', 'rb') as f:
        txt = f.readlines()
        for line in txt:
            key.append(unhexlify(line.strip()))

    pq = []
    with open(r'p_and_q','r') as f:
        txt = f.readlines()
        for i in range(0,len(txt),2):
            (p,q) = int(txt[i]),int(txt[i+1])
            pq.append((p,q))

    # for i in range(len(modulus)):
    #    assert(modulus[i] == pq[i][0]*pq[i][1]) and isPrime(pq[i][0]) and isPrime(pq[i][1])

    new = []
    with open(r'new.txt','r') as f:
        txt = f.readlines()
        for line in txt:
            new.append(unhexlify(line.strip()))

    return modulus, key, pq, new

def dec_RSA(c,pq):
    e = 17
    m = []
    for i in range(24):
        try:
            p, q = pq[i][0], pq[i][1]
            d = invert(e, (p-1)*(q-1))
            m.append(int(pow(c[i], d, p*q)))
        except:
            pass

    return m

def gen_init(seed):
    var = 0
    binseed = bin(seed)[2:]
    for each in binseed:
        var = var << 1
        if each == '1':
            var = var ^ seed
        if (var >> 256) != 0:
            var = var ^ 0x10000000000000000000000000000000000000000000000000000000000000223
    return var

def dec_init_state(m):
    while True:
        m = gen_init(m)
        if b"flag" in long_to_bytes(m):
            print(long_to_bytes(m))
            break

modulus, key, pq, new = ReadFile()
rsac = dec_CBC(key, new)
print(f'modulus = {modulus}')
print(f'rsac = {rsac}')
m = dec_RSA(rsac, pq)
print(m[0])
dec_init_state(m[0])

根据题目中RSA的参数的特点，即使用同一个加密指数e加密同一个明文，这样是可以通过低加密指数广播攻击（Hastad攻击）破解的，代码如下：

#sage
modulus = [98814919313645615562227632501842353623335365853705229901835148468883495797275597414884229673154676216661172834551301610934651963240119409868685277777800714566912405986645043974924445077030680918856209854280255930507129711147257107127165995928330446921396988707590674551893978543347857267274126479566133964621, 120309037005681976370949305207133746746983392014859786008077885868206237066288839457678467372792330832240493847319506910624107293327355575990265009395111812157069795648694878932912724266067108352114568041606927740805295578389613410752347225302683181568493377905133685788806771897944116380798383235212880787111, 111785936365127017878364692255320290881390250034420261152076893236497751708479451558829998875477413370296672127312833416766071239043340476618512716523841455668113510503541200502811971438914643566444202595134432922460265282115077045761511350952491133678485898016929814918158114380643876728495327499109907572429, 79107360215620077532659896175026195404235793190726547917783395438823337589603205953575483353228931287967504796791548380004359471560051416284517914649068134828827258371600937675407475086859499975654685415750272651221034077150245371035999615125332427139552452769011676593964204925071318469088799724530215124831, 76569172668426111655559325602270543124911618387292779930876870738135074619169375835923184222768365842868492168017456879360896599138595315395127482484106260530315856131196505195380380922891702380525990613251179620270889682827012451440651535676227547036408820876146886053832887455868205776680614430725735043793, 103550587454386321582558194662757829135212617455098189704465201424747083811259424236094773443146797074227050243796231001527513188517222102533609879856271977599085359214761995812013304273705087884012864870860316140959386263712261023431338642036955538675194995254860356196860928948904910104782072744666235086537, 90971837642433291280873621883216367817998065218607475308728029342384397984877685262773211911225017685122069795492703551175449897609664953357038478590596118164908410836795589316859218558924908109018646584994451050418244132783990484997446700555849562546557811117907782116545477224921738603975274933186794342491, 73413351017881312712468977975284224969712424335838849844092642943213311672854945671322891541815396298565073974489398966168460398863368939081968582617939378670552898186310210195570878457837228086549976345444751087428844389630498481701518885699105988150105202350202767346091098175295783591431654750734894877399, 71566039368566410696192366523253937232453984906766927106190688497758283492117264515150487759343943529526150027981496199751072735188260477291107672692545413595715319871286731540613403720279178498965086799594314786942108180966532474527957866789627251162692053119249102334395349645969466674380262856097693438521, 107628356419937581357884846311454393897766095193524472406415741434987693671384322405146875604772875861371298399663792861133695195849541253920791194728970646177177601304422827790522809107774220027822016584419667805968358988156290174765868439478153696514808349459959439415529354636614886500694506023255079823373, 91790474865200416562498525223387195736004778541952759476953293702991209352845230506773341766471835481185571572235140157043225934157398559619371693860888447188748144001978514611594339471810299348783446801794220036396407380964251612645759456101262295721935493095278291895678614455197784652961018115949658419209, 57745662696838303754303952465503228135078930819394673548775585096093512474118594638537980679427929033618503594855631276864271074749153391716985704043006635120113738881223783140512431675306017867810186495417036064170392661338259312054070420545443175282250796188844807847223002952495291671792316319261526203977, 74932280401824987073956870313685377085306206587423235348665346009152728684240450812927074555554879023572849407016961782430835249861002565952666939003777340922054220851625176505153442063005452154788416303298829441483147485245199232639360652800187172042662155481290924850141197767078965685536829327773869523877, 151358344215033244675875489778202324190602535755100062795559941742660074031432793530151212013764307368624092680307412309928239344375084702784223862577115959360359550888626830285200297868200193432953229394288774622849280647658223840091169768900707469559531106032962678397359686688885464319205469445395775505261, 58689109871391516446867152324943075006307619674297402783356934482330092148515973708298623302336452436909987582230530380141926976193048683919739669740152340284783548654140031841997682049142230063299924009372163169151602233027862127015614058254349505308306391730351101028876962457506249662645940599043284890479, 75861752129011706039232551442557324749632957472023260501544821732788259510015930776827063124846257933592600211419172200445500819665741080443558399298477165580569304097320488157982369509484537407955071525374169099071933569693698855275672496186292197585298047755984716638462181339492749181406670186116294083207, 95346418806667240579084074666101586656652563700979849442906833893357500903462274404419599353579163690013564626109399908623932855557157233581946448703748443415302152330984340846031484190075840945839657868726300498034388094371265188156182339601979104590181781634872909781460522645431312963619475713195057529053, 111263984476673436627489757275903278242507559263558167504820261180694675496975214444112803028740397579682261168188209236682419315487324285379489604372214244677171978542867983223205255696183564627476468236388981120865570003958834885830340089377367925355956102357809150294822256788916694056156982524732649022121, 96342125779778036941833551361632436941989127906210900570779845131168275089639216016217308560788807120832119537472979904464676694024827555869317191603939804273190020844614998671864808084618549460537796585180744783403305042282594096501853485099449520451347637383758909023665498253598410753186362009460492830077, 123521857465916800677857353280191063787794382070207831208108072146961113332349472274610835066727682678338330153931986264103329376246220375119477195903647449590640978718531623595252346576912612285734791871663640158415800617586885197074330899616507185403383799265717845801374846656401529390641443616981589591271, 131405795868049704946945078209025643754825946515862168268539786167707046891586623717476673108436285639575419309084969446295535565904197185085776823271112656565198238246280988380382110403894156666473014985911785626169140414905488725615795364652211328520244008235414509954941587909513975543894548408022461287151, 70967114730909286832264494950640090470702806737946498609585048455374288588521539757280256786923900427556094520842779667859333365003824139739221992299308163341116429010529334098884182035133381995880826298540167736908299468072146475041847885773746257305103221598524542443653591683985019129894558266194325182821, 107979432465960445003549108683102634118917861056034954024622240724163563602890130060316628069849623795318199576811119794560257267198435021465634488362082571221559448800322437539178387390819167699914898519745802727807447711037649579119174492560260601959406822151422632429549878526990294167401411360169366398309, 118859893624530448832013335940179713922013208072805796098733098460272093097271354351290476904722130296985679088987020794135009361338702308650147800222344594443187427748099291365938946361540610154000110289387874941903994296345375923386002742685159036859796319092682744673080262820281354319298093885235987771731]
rsac = [74504458879652943718663653850001437748341706690464761040767162486051250985910710402432140664943614478998161249571034628851708336587661498323826689121364093982543580220191566185998828898605279747505344794840238227684405607409399902867487210576304571314924605590164238090018623295565709785325901829375477233824, 90677687219451530935331531248712316796517647127110471932385574260084489206678436536025506136368980291362036895801209630370143728770276253819338126007059869043902337086043255709746216137616247630906044373779975724955439086975040791603062792477039660332639822636527898261073298224224617779978714534530831926382, 10441054926050260515775358807238672134995234707241729080928053791607295564961937959033050961406260156072418199349907188140011493317693815061021500276765874984758886044928346932845924300744885188311089620531981448619278771578819713090509906031204293324113030585264611939296118692099522756767915057220802371922, 75065942418049435620654589688902391988060904032224001083231877620990198917295603935365374839889910973316542865166711278558219477270958110193289958891670566730226744983567315102048352813458563913653693662545337119770268597757415606316643719527194000516770694472830033240065407861002018776722640989245914933864, 15967158178072756422697064801486297052470586035506805260212161467461991259373987383255280185122289231578694016246952580063663344331526433996641826455260971239990061316068805505099845909759948602603228604199884069913782124385897091085229540639182230053801383267057411228014418697121534096948589529087973618030, 37689478205889636617142877564157174378274716740702285559079324695046266180134126621576800675259844590798526867151978596131919317434518210642866030066928530109056429979286677519091178622240424270292632823938720664459741648575643188292206339090139580383397462178781885540845296443902839519200711798152861266216, 89991079171246842344250963909361678745600967560853729184873707321755423054752908194189661108220419993798870795216751075958380000036114708766326933569202097724367289862510179697851125292225500668270519323126824977283310811921738440461634618096070254683166891178610983021175889405723063903744760830044483553015, 12564784640138976223050478455073663507636463279004472970307500669890867813114565499438039688204577264309094677815359383327303659158283614635750329846385518405508451739233890320129606029814764719198822399536313264962983904837928212526895349327777003147602280321802339650663070755926837928479100067496182740015, 11644943444021682061705775758222178592151216531043485095365213895064672411659588784299149458722852375507456625497581474106874839986786922479523762090697979412491760703258217221044871874588203242834670991968225018330747687499319134596164253217457822290251577010138433021634093698922228165988834742170304034937, 7440952483263968136543488133538954176720150568935036124555561636558405472861937899311692100225854466894641991674736586071693917092584709253652133242676032360332823213448817914514598770449974685391866088874604994277625053485651836603598675134877502825868995744877182003110720548987649603439409541560443056233, 26432139649644724258156851399015803833287203554853089382176324578551505137460733413666096695203082335960652170254261514531360519569163381379304943388941105657952632544172898150281406145833476518212352728023813500749575869340588121411252877723139411912575077520300256718257321039492671708893676087174130127627, 57123543722088565652435248193112878912919477826104699980308653915041296324381912869705895816597336792356053129908891429078049803245912627548678533968825391714890250901090173610814507250901176738461218113028322059386190976395617728466608881544720668647826686193434008738860268283215016301583387030358145368979, 23345145988953014746994009332494104314006269768459845287686772564449193680626141627252617993162588712706111487450314527081815527083176603353888026799539264957926735851981959663747313504865883507010317064677343050012331837540653419457977282011143696513646910221917021350965089365064108284126991594769804195958, 18584786192890585340554251103045488911640395930311242880183603291612729344818076657431110151188845846461865668722727322657706096938157538175405143087120939463583993015116566820907628655632261436234097039735321279198185020071927791315164532898161858419324906856694850350127947939219274692570387210945622160425, 32032100783803280101506640700407146214507106934402623014894345433328319560672855179559658148321460290731133069045000363251832955885416381476803469919752501472790597059954145215453484924607402213833208606478061431892867099951406127186058725643977545110983793482369725606454118192673307075130629848277572761800, 33553261797062509715636247635116146924068973136236402732133070162363574617308632416380426301032863871980545883634361689918994364261326716216183140972627635354327281418414737356206607530518178640605226107447668012418064780102828536450110475122533604086967729782507101136102693107027580346060700369982449268926, 89670084243832433804089281202232826269625530193093980037641998743679243635754393741282858947768060115028683001038661205854054299192392452008668561209116501939507252886741566691289008796906111249663270020473187990112802944098815756041580119043386176229088695930061919546816589198630865246014946002351028640824, 1885172266369210136727710999528571764220354997431579368990444202265790166417523564316711055628257703430143702613679953660332632889708772965357813478003529054531405806804431450226099406126799278914742462302125596290589751898179861813384971843398481071872868293514166981185749346457303403593450424312260349932, 38315205924420685030274312234361688998295987101811658111889610086810814657639278790542984546365338373266315310027165402200622668761747894472059459061618323576723570481849451043583002607285263178217863197890339568464658591355554682896748372777684662342898583067137754082163049279790489618727974756059268134757, 1503390686484331392720378357968284034985922228277965470494601879150160036004097286813280072280703228267019910176646779550924896975837747296612147447328318954616213255299480731492038869675560914084449670874184183238901906564172317022457453828770471467222933579318607818146238931448210350167812730883209706573, 18261213979022925288437196949092892081418030897865208654146190002058335053744268642563789748028557517530508560801191795766191341328352904811764022501596832195139424135209021776110924124039296421367751450136220305469912616827010861330256881960646842786938701289977933762823676627250459890848839915051749826759, 23533732290079220996981259709972499473689463975286699510373965623743642991317196761881160594348850261577119383002784894244669591774257030880479791202186436732524028353661327508406190257273456035705131167830367903206715636687652856796934500412120422271222540504288448174980494038298906213387391904497984121223, 4947065111438996960526894808482046817149283280661743322149062731884606781783471692517417963283291589117647621522497791685498761948515564261734860969232487531299769159613422384551359597280388941714265690573934157839829726977812657605906204879891549647528887678395428467400579365987072840270925293902595715999, 67653403106052782639824505158253042492359705399959732418763452025230197898542624747634303715085261173616195255069462499517424774656996471734918800423899632652788451324107959871547187612032289791267004085024256214283694845473459442053468102390886723908204278002126105750462941050782644578760981771561025922699]
M = crt(rsac,modulus)
f = x^17 - M
print(f.roots())
#[(66869997917800083972572187953062445239249136563973495502684696601787248828812, 1)]

---

CTF-Training-Record-2 | 0xDktb’s Blog (dunkirkturbo.github.io)

RSA | Lazzaro (lazzzaro.github.io)

LCG(线性同余生成器)_WustHandy的博客-CSDN博客

浅谈Java的伪随机数发生器和线性同余法 - 简书 (jianshu.com)