多项式RSA

多项式RSA,唔

看下先知上的大佬

https://xz.aliyun.com/t/4545

多项式RSA

之前也一直认为多项式RSA和一般的RSA区别不大,也就是师傅说的RSA对于整数的体制可以适用于有限域上的多项式,主要是有一些多项式的概念

首先在有限域上选取两个不可约多项式$g(p),\ g(q)$

  • 有限域是什么:就理解成有限个数的集合
  • 有限域多项式是什么:就是系数属于某个有限域的多项式
  • 有限域下不可约多项式是什么:就是一个多项式不能被拆成多个同一有限域下多个多项式的乘积

计算$g(n)=g(p)\times g(q)$

计算$g(n)$的欧拉函数$phi=\varphi(g(n))$

选一个整数$e$,$(e,\ phi)=1$,并求出逆元$d$,$e\times d\equiv 1(mod\ phi)$

加密:$g(c)=g(m)^e\ mod\ g(n)$

解密:$g(m)=g(c)^d\ mod\ g(n)$

其中e和d都是整数,它们和多项式可以进行模幂运算


先知社区求phi有点问题,我很好奇多项式是怎么转多项式为整数的

所以更重要的问题是,如何求phi?,推导省略直接上结论,记$g(x)$的次数为$a$
$$
\varphi(g(x))=2^a-1
$$
还有个问题,现在遇到的这些都是多项式$g(n)$可以用sage直接分解的,那如果是考攻击方式呢,还是要学

最后如何把明文转换成多项式:将明文每个字符转ascii,作为多项式的系数

[watevrCTF 2019]Swedish RSA

之前倒也做过

https://4xwi11.github.io/posts/80806ae5/#unusualrsa3

之前跑脚本倒也能出来,就是要改下快速幂,不然很慢

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#!/usr/bin/env sage
# -*- coding: utf-8 -*-
p = 43753

R.<x> = PolynomialRing(GF(p))

N = 34036*x^177 + 23068*x^176 + 13147*x^175 + 36344*x^174 + 10045*x^173 + 41049*x^172 + 17786*x^171 + 16601*x^170 + 7929*x^169 + 37570*x^168 + 990*x^167 + 9622*x^166 + 39273*x^165 + 35284*x^164 + 15632*x^163 + 18850*x^162 + 8800*x^161 + 33148*x^160 + 12147*x^159 + 40487*x^158 + 6407*x^157 + 34111*x^156 + 8446*x^155 + 21908*x^154 + 16812*x^153 + 40624*x^152 + 43506*x^151 + 39116*x^150 + 33011*x^149 + 23914*x^148 + 2210*x^147 + 23196*x^146 + 43359*x^145 + 34455*x^144 + 17684*x^143 + 25262*x^142 + 982*x^141 + 24015*x^140 + 27968*x^139 + 37463*x^138 + 10667*x^137 + 39519*x^136 + 31176*x^135 + 27520*x^134 + 32118*x^133 + 8333*x^132 + 38945*x^131 + 34713*x^130 + 1107*x^129 + 43604*x^128 + 4433*x^127 + 18110*x^126 + 17658*x^125 + 32354*x^124 + 3219*x^123 + 40238*x^122 + 10439*x^121 + 3669*x^120 + 8713*x^119 + 21027*x^118 + 29480*x^117 + 5477*x^116 + 24332*x^115 + 43480*x^114 + 33406*x^113 + 43121*x^112 + 1114*x^111 + 17198*x^110 + 22829*x^109 + 24424*x^108 + 16523*x^107 + 20424*x^106 + 36206*x^105 + 41849*x^104 + 3584*x^103 + 26500*x^102 + 31897*x^101 + 34640*x^100 + 27449*x^99 + 30962*x^98 + 41434*x^97 + 22125*x^96 + 24314*x^95 + 3944*x^94 + 18400*x^93 + 38476*x^92 + 28904*x^91 + 27936*x^90 + 41867*x^89 + 25573*x^88 + 25659*x^87 + 33443*x^86 + 18435*x^85 + 5934*x^84 + 38030*x^83 + 17563*x^82 + 24086*x^81 + 36782*x^80 + 20922*x^79 + 38933*x^78 + 23448*x^77 + 10599*x^76 + 7156*x^75 + 29044*x^74 + 23605*x^73 + 7657*x^72 + 28200*x^71 + 2431*x^70 + 3860*x^69 + 23259*x^68 + 14590*x^67 + 33631*x^66 + 15673*x^65 + 36049*x^64 + 29728*x^63 + 22413*x^62 + 18602*x^61 + 18557*x^60 + 23505*x^59 + 17642*x^58 + 12595*x^57 + 17255*x^56 + 15316*x^55 + 8948*x^54 + 38*x^53 + 40329*x^52 + 9823*x^51 + 5798*x^50 + 6379*x^49 + 8662*x^48 + 34640*x^47 + 38321*x^46 + 18760*x^45 + 13135*x^44 + 15926*x^43 + 34952*x^42 + 28940*x^41 + 13558*x^40 + 42579*x^39 + 38015*x^38 + 33788*x^37 + 12381*x^36 + 195*x^35 + 13709*x^34 + 31500*x^33 + 32994*x^32 + 30486*x^31 + 40414*x^30 + 2578*x^29 + 30525*x^28 + 43067*x^27 + 6195*x^26 + 36288*x^25 + 23236*x^24 + 21493*x^23 + 15808*x^22 + 34500*x^21 + 6390*x^20 + 42994*x^19 + 42151*x^18 + 19248*x^17 + 19291*x^16 + 8124*x^15 + 40161*x^14 + 24726*x^13 + 31874*x^12 + 30272*x^11 + 30761*x^10 + 2296*x^9 + 11017*x^8 + 16559*x^7 + 28949*x^6 + 40499*x^5 + 22377*x^4 + 33628*x^3 + 30598*x^2 + 4386*x + 23814
c = 5209*x^176 + 10881*x^175 + 31096*x^174 + 23354*x^173 + 28337*x^172 + 15982*x^171 + 13515*x^170 + 21641*x^169 + 10254*x^168 + 34588*x^167 + 27434*x^166 + 29552*x^165 + 7105*x^164 + 22604*x^163 + 41253*x^162 + 42675*x^161 + 21153*x^160 + 32838*x^159 + 34391*x^158 + 832*x^157 + 720*x^156 + 22883*x^155 + 19236*x^154 + 33772*x^153 + 5020*x^152 + 17943*x^151 + 26967*x^150 + 30847*x^149 + 10306*x^148 + 33966*x^147 + 43255*x^146 + 20342*x^145 + 4474*x^144 + 3490*x^143 + 38033*x^142 + 11224*x^141 + 30565*x^140 + 31967*x^139 + 32382*x^138 + 9759*x^137 + 1030*x^136 + 32122*x^135 + 42614*x^134 + 14280*x^133 + 16533*x^132 + 32676*x^131 + 43070*x^130 + 36009*x^129 + 28497*x^128 + 2940*x^127 + 9747*x^126 + 22758*x^125 + 16615*x^124 + 14086*x^123 + 13038*x^122 + 39603*x^121 + 36260*x^120 + 32502*x^119 + 17619*x^118 + 17700*x^117 + 15083*x^116 + 11311*x^115 + 36496*x^114 + 1300*x^113 + 13601*x^112 + 43425*x^111 + 10376*x^110 + 11551*x^109 + 13684*x^108 + 14955*x^107 + 6661*x^106 + 12674*x^105 + 21534*x^104 + 32132*x^103 + 34135*x^102 + 43684*x^101 + 837*x^100 + 29311*x^99 + 4849*x^98 + 26632*x^97 + 26662*x^96 + 10159*x^95 + 32657*x^94 + 12149*x^93 + 17858*x^92 + 35805*x^91 + 19391*x^90 + 30884*x^89 + 42039*x^88 + 17292*x^87 + 4694*x^86 + 1497*x^85 + 1744*x^84 + 31071*x^83 + 26246*x^82 + 24402*x^81 + 22068*x^80 + 39263*x^79 + 23703*x^78 + 21484*x^77 + 12241*x^76 + 28821*x^75 + 32886*x^74 + 43075*x^73 + 35741*x^72 + 19936*x^71 + 37219*x^70 + 33411*x^69 + 8301*x^68 + 12949*x^67 + 28611*x^66 + 42654*x^65 + 6910*x^64 + 18523*x^63 + 31144*x^62 + 21398*x^61 + 36298*x^60 + 27158*x^59 + 918*x^58 + 38601*x^57 + 4269*x^56 + 5699*x^55 + 36444*x^54 + 34791*x^53 + 37978*x^52 + 32481*x^51 + 8039*x^50 + 11012*x^49 + 11454*x^48 + 30450*x^47 + 1381*x^46 + 32403*x^45 + 8202*x^44 + 8404*x^43 + 37648*x^42 + 43696*x^41 + 34237*x^40 + 36490*x^39 + 41423*x^38 + 35792*x^37 + 36950*x^36 + 31086*x^35 + 38970*x^34 + 12439*x^33 + 7963*x^32 + 16150*x^31 + 11382*x^30 + 3038*x^29 + 20157*x^28 + 23531*x^27 + 32866*x^26 + 5428*x^25 + 21132*x^24 + 13443*x^23 + 28909*x^22 + 42716*x^21 + 6567*x^20 + 24744*x^19 + 8727*x^18 + 14895*x^17 + 28172*x^16 + 30903*x^15 + 26608*x^14 + 27314*x^13 + 42224*x^12 + 42551*x^11 + 37726*x^10 + 11203*x^9 + 36816*x^8 + 5537*x^7 + 20301*x^6 + 17591*x^5 + 41279*x^4 + 7999*x^3 + 33753*x^2 + 34551*x + 9659
S.<x> = R.quotient(N)

P, Q = N.factor()
P, Q = P[0], Q[0]
phi = (p ** P.degree() - 1) * (p ** Q.degree() - 1)
e = 0x10001
d = inverse_mod(e, phi)

m = pow(c, d, N)
m = "".join([chr(c) for c in m.list()])
print(m)

flag{RSA_from_ikea_is_fun_but_insecure#k20944uehdjfnjd335uro}

[0CTF 2019]baby rsa

这道题主要看下不同的姿势

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#!/usr/bin/env sage
# coding=utf-8

from pubkey import P, n, e
from secret import flag
from os import urandom

R.<a> = GF(2^2049)

def encrypt(m):
global n
assert len(m) <= 256
m_int = Integer(m.encode('hex'), 16)
m_poly = P(R.fetch_int(m_int))
c_poly = pow(m_poly, e, n)
c_int = R(c_poly).integer_representation()
c = format(c_int, '0256x').decode('hex')
return c

if __name__ == '__main__':
ptext = flag + os.urandom(256-len(flag))
ctext = encrypt(ptext)
with open('flag.enc', 'wb') as f:
f.write(ctext)

这个还是python2吧,我现在sage用不了python2的,emmmm就这样吧,过程是一模一样的