尝试着对N分解

模量对数

看起来像形式的数字$N = (2^M + a)(2^M + b)(2^M + c)(2^M + d) $.

日志基 2 的弹性模量是 5568 所以$M=1392$.

我们现在可以做一些数学,看看什么信息,我们可以摆脱 4 二进制序列︰

 

$$ N = (2^M + a)(2^M +b)(2^M +c)(2^M +d) $$

 

$$ N = 2^{4M} + 2^{3M}(a + b + c + d) + 2^{2M}(ab + ac + ad + bc + bd + cd) + 2^M(bcd + acd + abd + abc) + abcd $$

 

让︰

$$ p = a + b + c + d $$

 

$$ q = ab + ac + ad + bc + bd + cd $$

 

$$ r = bcd + acd + abd + abc $$

 

$$ s = abcd $$

 

你会忍不住想上述 4 的二进制字符序列对应直接到$p$, $q$, $r$, $s$ ,但这里面有蹊跷︰ 只有$s$等于其各自的二进制序列。

其他的可能会在 0 或更多,因为奇数偶数有甚至总和。我们可以只是强制性,但它,所以我们会担心以后。

我们如何找出$a$, $b$,$c$和$d$给定$p$, $q$, $r$ , $s$?高中数学的救援︰

 

$$ (X - x_1)(X - x_2)(X - x_3)(X - x_4) = 0 $$

 

$$ X^4 -(x_1 + x_2 + x_3 + x_4)X^3 + (x_1 x_2 + x_1 x_3 + x_1 x_4 + x_2 x_3 + x_2 x_4 + x_3 x_4)X^2 - (x_2 x_3 x_4 + x_1 x_3 x_4 + x_1 x_2 x_4 + x_1 x_2 x_3)X + x_1 x_2 x_3 x_4 = 0 $$

 import math

import gmpy2

gmpy2.get_context().precision=5000

from polycubicroot import *

def Carpenter(p, q,r, s):

p = gmpy2.mpfr(p)

q = gmpy2.mpfr(q)

r = gmpy2.mpfr(r)

s = gmpy2.mpfr(s)

"""

Solves for all roots of the quartic polynomial P(x) = x^4 + px^3 + qx^2 + rx + s.

"""

#print "@@@ inside Carpenter", p,q,r,s

pby4 = p/4.0

C = ((6 * pby4) - 3*p)*pby4 + q

D = (((-4*pby4) + 3*p)*pby4 - 2*q)*pby4 + r

E = (((pby4 - p)* pby4 + q)*pby4 - r)*pby4 + s

#print "C, D, E=",C, D, E

root = None

for zero in polyCubicRoots(2*C, (C**2 - 4*E), -D**2):

#print "zero = ", zero

if type(zero)== type(gmpy2.mpfr(1.0)) and zero > 0.0:

root = zero

#print "found a positive root."

break

if root == None:

return None

sqroot = gmpy2.sqrt(root)

Q1 = -root/4.0 - C/2.0 - D/2.0 / sqroot

Q2 = -root/4.0 - C/2.0 + D/2.0 / sqroot

#print "Q1,Q2=", Q1, Q2

sqy2 = sqroot/2.0

if Q1 >= 0.0:

sqQ1 = gmpy2.sqrt(Q1)

z1 = sqy2 + sqQ1 -pby4

z2 = sqy2 - sqQ1 -pby4

else:

sqQ1 = gmpy2.sqrt(-Q1)

z1 = (sqy2-pby4, sqQ1)

z2 = (sqy2-pby4, - sqQ1)

if Q2 >= 0.0:

sqQ2 = gmpy2.sqrt(Q2)

z3 = -sqy2 - sqQ2 -pby4

z4 = -sqy2 + sqQ2 -pby4

else:

sqQ2 = gmpy2.sqrt(-Q2)

z3 = (-sqy2-pby4, sqQ2)

z4 = (-sqy2-pby4, -sqQ2)

return (z1, z2,z3, z4) 

得到一个 4 元组解和循环的左侧和右侧的任何 4 根,看看是否我们得到的除数$s$,应完全$a b c d$。如果我们得到一个然后基本上解决问题。

剩下的唯一问题是,我们不知道多少零点的每个$p$, $q$ ,$r$有。让我们试着从 3 零 0 零的所有组合︰

 p= 0b10001110000110111100100111111000100111

q= 0b1110110010101000100001010011110000010100100010111011100111100011010001010101

r= 0b1010111100101001100011011101101000000110011010100010001010001100010000111001010011110111011000110010000110010001

s= 0b11000010011110000010000010000101010000011101100011101110110110011111000000001011001101111100111001111110001100100101101010011011011101110111001110101

A=[]

B=[]

C=[]

D=[s]

for i in range(0,3):

A.append(p * (2**i))

B.append(q * (2**i))

C.append(r * (2**i))

for i in A:

print "===================="

for j in B:

for k in C:

for l in D:

(x1, x2, x3, x4) = Carpenter(-i,j,-k,l)

# since sometimes the solution will consist of complex numbers, we'll just disregard those with a try-except

try:

#approximate value of x1

aprox = int(x1.__floor__())

for step in range(0,10000):

#try to the right

if s % (aprox + step) == 0:

print aprox + step

#and to the left

if s % (aprox - step) == 0:

print aprox - step

except:

pass 

这样我们得到了所有的四个因素 !让我们看一下这些实际上将弥补$N$. 而且刚好对应6个密文

通常情况下,密文的内容有关于同一密钥作为弹性模量,但在这种情况下他们不。这意味着,要么

 

指数是小 (说 3) 和消息$m$是真的很短。但然后还有一个主要的问题︰ 因为根本不会被加密明文$m^3$将小于$N$所以$ m^3 $等于$ m^3 \bmod N $(没有加密 = = 坏)

指数是一个体面的大小 (通常是 65537) 但模量不是$N$。那么它是什么?提示︰ 密码密钥,大约是一半的模量。

由于有 4 质数我们可以作出以下模量︰ $ab $ $ ac $ $ ad $ $ bc $ $ bd $ $ cd$。六模量,六个密码文本 !

 # -*- coding: utf-8 -*-

import gmpy2

f1 = 108082147276398906822234149167480016132157014049560913761488880190018027488520386318253742675423286348552334110023434741671427911613197684395221211646299519273129194692306445874938199068586137486874290442314459278649345469626426790676801658394799404284116771456479272808343825651929906737811050557836671896732124546721747709022607151231423494815945385193624295868730390462068156825588342737037490320356361648437686599733

f2 = 108082147276398906822234149167480016132157014049560913761488880190018027488520386318253742675423286348552334110023434741671427911613197684395221211646299519273129194692306445874938199068586137486874290442314459278649345469626426790676801658394799404284116771456479272808343825651929906737811050557836671896732124546721747709022607151231423494815945385193624295868730390462068156825588342737037490320356361648437686598461

f3 = 108082147276398906822234149167480016132157014049560913761488880190018027488520386318253742675423286348552334110023434741671427911613197684395221211646299519273129194692306445874938199068586137486874290442314459278649345469626426790676801658394799404284116771456479272808343825651929906737811050557836671896732124546721747709022607151231423494815945385193624295868730390462068156825588342737037490320356361648437686597791

f4 = 108082147276398906822234149167480016132157014049560913761488880190018027488520386318253742675423286348552334110023434741671427911613197684395221211646299519273129194692306445874938199068586137486874290442314459278649345469626426790676801658394799404284116771456479272808343825651929906737811050557836671896732124546721747709022607151231423494815945385193624295868730390462068156825588342737037490320356361648437686600843


e = 65537



N = 136463296143190893248608270448493439350683115492680876168052084053504347848230208722375209906076869052896867483336405778205506777456239889195254751404720423599579856449118314029926341504368322006603240157122006887052352260584975471045726061549619820648607756554188235927302932154082823424745427535138517580059079182622982686168676727690710935334448342460007367100561867135456783067679052102951400317012276135721843672557488711786097028300122487504246207343408690682175135816894247936690735246673985277504237071409859401185555290479154689954442396078547166388871978321863215123445269948324347122830270551854130365741961149443091305418900821360286967705810624380568422193310901491451664233271486835428015602712828527839237760712498204208114606471362410690870710499020885304151928570632315330437235330924071236528549152143092328833484016372976817809299430339752106123272706667690980774118545338761390919046832338928913059106351087015273177895380149217373395580948428521961929052291618261409715145038026920685297885235683434107218249548518659574493203836870070093674704878498465104238178877833471640168999551981025958271865584457582649595664499635489167898398826429084686279399959537724187268210760718340639939389766681703213695409551029265784749153180083564347733676434492122290166926822855552175712346350104533901079605669192289178418165584907326210349152609265563881542151049862642882025360604692084264752182798892702414638180781403398216616666472863758371330058299406233359567750413748257953598843651612399709945608339073191578573877985362619301768016485017815171486743934037935902150228210340093187387036580763941637989511155597643722984057627086517479392172108031663245553269


enc_1 = 7106898334865955962704663230185766445951889978440527670379641714370681285859949869949187832359082523864224641583685587358279064795569170851524374568027152395396233789347594775999482749460592054691082921627513982308507181335532299134140407681024881476418889411780375090299905813982101694827597560498543197874412334623795312307111560405270260391658994764065881380399694265015620683173527502434421206862766543229116921174206929733891873772589067987314963792051855633244006474202333168597001157421208180748203884266562430752691702675420434792273754214010918653607624500201387229281379420620532777072560178585294886033718995698223904867539921848198115466603585461755489085844144950962514847839122794545452937035169471880080923607755994138855467643267829059636266176328056201003864357129609343207959211080595752950950566686954867562406898169012


enc_2 = 6049049661741129561339303988250162617703359741970199356749378099535308799521119296163475813567458644038456685905251522625056377260310087845057811228022836098917570328692580410899852889868960996513905266043335963520913743708134923879544500911079066640658342641576456724637857109609913138972587873848795314132791317122747052648231297078735128282339170389129703582587817548539040826603188468662975329145727078616857156409325283263490433476018586450960082502578543327451065633585123695731081960986876439520499678158646526292218543279767834119677467758578802705169018711527506297869276113561542222807369071584959189923897216079505316482443445467837921144205079761354928950270172051270453170856002545491432278972735662895438668870901370521394906635478044848448535690635490093836659267778026686404695474454443310769209580317339039949689309577128


enc_3 = 9297802808564228678857927735224258610176831223455462482108153962953283311112501933779642540831558523911908205264682548531027493458025348252477502958948277516597689610204247227516319189048436710254675204218913508162139428248916620471317757210444645620644754294112426431692939788347835259617673728076204145049918767636122119264147566892091600628134179775710906591426338082246629946748851355701691716873854064848390273287305765646761438968986164159947841015011854342290060053810459830057357847548324695563067411557873081187572229935066117850179208775004384867270372650455853756560763012162682268812544173997311505136324203900399349629488710197844813293107115270398692552357803651576615589484454781227778727051440858478438251726051391317986762487421941570502251822920317312304622541764818356928105898291743494415190324388360012261032469805293


enc_4 = 713095983409993528016630065648951013409887429450761159296479210782308084847050785300379490902448647458053364322993274237841476340954537003347555548992827654062094884577630320399338426853024680425709980978726290825928571411715417634212022523987025390940108095446209802316068849127107378425087055832984628808129531097287891984529260048649164000341136589805930287941174070455962380115617312855801447326371361475429811263285218112383055283949280091896985779211927696867430269968278138068400828124612158603851472016327854927370226178776190765638542240547246882872033038792494915187774790763271179846203704834184269540668646905004118327597860873987248913148268250014480899515845595580486997925049895214602419037682253683176691877538075243485739730794370764108792093424342949560517002862934953109055108423633725444594683266260073663364732952255


enc_5 = 10309778311674135836145162475142299890445328570998831868156889990227275287204954712195141311549279047953844775828171871944522109110470024787792366772581241453340259883183812924297131077506375091086889140550405275547002202216935333211274901846970064522877611909017778486075399188006657623263902100044828896866180655435221665929435914366779334701622735670714649165956831390471034827078404866534094264914677879030956272977839491780410171625330771079943455183946885337962048237633491024513227027839179415230496573264968451527246966618074421625677382526573096067979952606553854268016651712174361578916100364115941853700612277618158243626702349480460819792765645689509997114148748479096516230468934427015454217368508102362912163051749856763103972010705773880053579573724226945229453471505368052572019992934401394664840254259798167531746190494146


enc_6 = 8939535907261295438433886577386432968291926162277924912979941380189504000322310159787894619015550096747658897136943700072192920334615223423230154197591756541966832740944457435736068401948276698864982347929802551347213730712997519211436818145872722485367264219104124473346589051164722340414948298088909961344463800461486219156960782319672049123860381674970981713865865119998917955886468613202521879160392276542945726096267432761588212550950818569769983241315782390152313705093940640027041352082844550311829177150159737347964813330180325283882516072009654288888676591648012847062527444169352000893928289409020106115561912814987882374652419114381836807085680725260815445689968522849732254659773192714360607196619281714422460754645088867512471482029657153787836396684484646302575186890717770078233479877360251173401000006298555695416782863190


N = f3 * f4

phi = (f3-1)*(f4-1)

d = gmpy2.invert(e, phi)

print `hex(pow(enc_1, d, N))`[3:-1].decode('hex')


N = f2 * f4

phi = (f2-1)*(f4-1)

d = gmpy2.invert(e, phi)

print `hex(pow(enc_2, d, N))`[3:-1].decode('hex')


N = f1 * f4

phi = (f1-1)*(f4-1)

d = gmpy2.invert(e, phi)

print `hex(pow(enc_3, d, N))`[3:-1].decode('hex')

N = f1 * f3

phi = (f1-1)*(f3-1)

d = gmpy2.invert(e, phi)

print `hex(pow(enc_4, d, N))`[3:-1].decode('hex')


N = f1 * f2

phi = (f1-1)*(f2-1)

d = gmpy2.invert(e, phi)

print `hex(pow(enc_5, d, N))`[3:-1].decode('hex')


N = f2 * f3

phi = (f2-1)*(f3-1)

d = gmpy2.invert(e, phi)

print `hex(pow(enc_6, d, N))`[3:-1].decode('hex') 

最终简单的拿到了flag

Flag:

温馨提示: 此处内容需要评论本文后刷新才能查看,支付2元即可直接查看所有Flag。

小广告:关于获取西普实验吧所有Flag请点击这里查看索引

查看所有Flag文章需要输入密码,需要获取文章密码的童鞋请扫描下面微信或支付宝二维码捐助至少2元(老哥,捐多捐少是个缘分)之后发送支付凭证号联系我获取,Flag大全地址:Flag大全

新功能:捐款的小伙伴请联系我把自己的注册邮箱加入网站白名单,可以免回复看到本站所有Flag

PS:本站不是实验吧的官方站点,纯粹是个人博客,收取Flag费用仅是维持服务器费用,做站不易,且行窃珍惜!

微信二维码:
支付宝二维码: