由suctf一道题学到的中国余子式定理

文章以word形式发至邮箱:

minwei.wang@dbappsecurity.com.cn

有偿投稿,记得留下你的姓名联系方式哦~

中国余式定理即俗称的韩信点兵,又称孙子点兵、鬼谷算、秦王暗点兵,在先秦战国时代就已经有了记载。

有一道题,是这样写的:

“今有物不知其数,三三数之余二,五五数之余三,七七数之余二,问物几何?”,这首诗的意思是有一个数,除以三余数为二,除以五余数问三,除以七余数为二,求这个数。

解法:

①令除数n1=3,n2=5,n3=7两两互质,然后将除数相乘得到一个n,n=n1n2n3=105;

②令余数x1=2,x2=3,x3=2,令乘积除以每个除数,得到一组数,M1=n/n1=105/3=35,M2=n/n2=105/5=21,M3=n/n3=105/7=15;

③利用辗转相除法或直接计算乘法反元素得到一组数:

s1=(mod n1) = ≡ 2 (mod 3)

s2=(mod n2) = ≡ 1 (mod 5)

s3=(mod n3) = ≡ 1 (mod 7)

④最后将每对M、x、s求乘积并将每对数据相加求和,将结果对n取余数,就可以得到最终的结果。

X = (x1M1s1 + x2M2s2 + x3M3s3) (mod n)

= (2×35×2 + 3×21×1 + 2×15×1) (mod 105)

= 23

中国余式定理:令n1、n2、……、nk为两两互质的整数,令n=n1n2……nk。联立方程组:

在集合{0,1,2……n-1}有唯一解:

x=

其中Mi=n/ni,si(mod ni) (n=0,1,2,…k)

上边这道题用程序来解的话是这样的:

import gmpy2

n = [3,5,7]

x = [2,3,2]

N = 1

for i in n:

N *= i

M = []

for i in n:

M.append(N/i)

s = []

for i in range(len(n)):

s.append(gmpy2.invert(M[i],n[i]))

#print s

sum = 0

for i in range(len(n)):

sum += x[i] * M[i] * s[i]

X = sum % N

print X

运行结果:

看suctf的一道题目:

Game.py内容:

import flag

flag = flag.flag

sands = int(flag[5:-1].encode("hex"), 16)

holes = [257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373]

with open("sand.txt", "w") as f:

for i in range(len(holes)):

sand = sands % holes[i]

f.write(str(sand)+"\n")

意思是将flag{}中的内容进行十六进制,然后转换成十进制对holes中的数据做求余运算,放入sand.txt中。利用中国余子式定理可以得到flag。

还是上边的脚本,稍作修改:

#coding:utf-8

import gmpy2

with open('sand.txt','r') as f:

sand_src = f.readlines()

sands = []

for i in sand_src:

sands.append(int(i.replace('\n','')))

holes = [257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373]

n = 1

for i in holes:

n *= i

M = []

for i in holes:

M.append(n/i)

s = []

for i in range(len(holes)):

s.append(gmpy2.invert(M[i],holes[i]))

#print s

x = 0

for i in range(len(sands)):

x += sands[i] * M[i] * s[i]

res = x % n

#print res

encode_hex = hex(res).replace('0x','').replace('L','')

decode_hex = encode_hex.decode('hex')

flag = "flag{" + decode_hex + "}"

print flag

运行结果:

题目虽不是很难,但对于我来说这个定理也是头一次听说,头一次接触,倒也学到了不少。

-END-

原文发布于微信公众号 - 安恒网络空间安全讲武堂(cyberslab)

原文发表时间:2018-06-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数说工作室

【SAS Says】基础篇:8. 相关、回归等初步统计

SAS是一个专业的统计软件,前面我们介绍了很多数据管理、输出美化的东西,本节终于要介绍一点SAS做统计的知识了,不过,在基础篇中我们只大概介绍一下,更多统计分析...

2686
来自专栏ATYUN订阅号

使用Python计算非参数的秩相关

当两个变量都有良好理解的高斯分布时,很容易计算和解释。而当我们不知道变量的分布时,我们必须使用非参数的秩相关(Rank Correlation,或称为等级相关)...

883
来自专栏大数据挖掘DT机器学习

Kaggle案例——使用scikit-learn解决DigitRecognition问题

1、scikit-learn简介 scikit-learn是一个基于NumPy、SciPy、Matplotlib的开源机器学习工具包,采用Python语言编写,...

39111
来自专栏人工智能LeadAI

决策树会有哪些特性?

决策树(Decision Tree)是机器学习中最常见的算法, 因为决策树的结果简单,容易理解, 因此应用超级广泛, 但是机器学习的专家们在设计决策树的时候会考...

2937
来自专栏小樱的经验随笔

洛谷 2634&&BZOJ 2152: 聪聪可可【点分治学习+超详细注释】

2152: 聪聪可可 Time Limit: 3 Sec  Memory Limit: 259 MB Submit: 3435  Solved: 1776 [S...

2626
来自专栏ACM算法日常

最短路(Floyd算法的动态规划本质)- HDU 2544

Floyd–Warshall(简称Floyd算法)是一种著名的解决任意两点间的最短路径(All Paris Shortest Paths,APS...

561
来自专栏数据结构与算法

P1498 南蛮图腾

题目描述 自从到了南蛮之地,孔明不仅把孟获收拾的服服帖帖,而且还发现了不少少数民族的智慧,他发现少数民族的图腾往往有着一种分形的效果(看Hint),在得到了酋长...

3558
来自专栏人工智能LeadAI

NLP系列学习:前向算法和后向算法

在这一篇文章里,我们可以看到HMM经过发展之后是CRF产生的条件,因此我们需要学好隐马尔科夫模型.

663
来自专栏zhisheng

学习算法之路

一个搞ACM的需要掌握的算法的sheet。 第一阶段:练经典常用算法,下面的每个算法给我打上十到二十遍,同时自己精简代码,因为太常用,所以要练到写时不用想,10...

3535
来自专栏CDA数据分析师

一篇文章教你如何用R进行数据挖掘

引言 R是一种广泛用于数据分析和统计计算的强大语言,于上世纪90年代开始发展起来。得益于全世界众多 爱好者的无尽努力,大家继而开发出了一种基于R但优于R基本文本...

2065

扫码关注云+社区