一道离散数学关于密码破解!假设a=13,b=35,m=87,Xo=19有一个公式Xn＋1=aXn+bmodm例如X₁=aXo+bmodm=21X₂=aX₁+bmodm=47X₃=aX₂+bmodm=37X₄=aX₃+bmodm=81X5=aX₄+bmodm=44

Question

一道离散数学关于密码破解! 假设a=13, b=35,m=87,Xo=19
有一个公式
Xn＋1=aXn +b mod m
例如
X₁=aXo + b mod m = 21
X₂=aX₁+ b mod m =47
X₃=aX₂+ b mod m =37
X₄=aX₃+ b mod m=81
X5 =aX₄+ b mod m=44
X6 =aX5 + b mod m=85
X7= aX6+ b mod m=09
X8=aX7+ b mod m=65
X9=aX8+ b mod m=10
X10=aX9+ b mod m=78
：
：
以此类推
假设26个英文字母分别以数字表示
比如a=01,b=02,c=03.x=24,y=25,z=26
假如我们把“this secret message is to.”进行加密,得到这样一个数据表
加密的信息： t h i s s e c r e t m e .
数字表示： 20 08 09 19 19 05 03 18 05 20 13 05
Xn(n≠0) ： 21 47 37 81 44 85 09 65 10 78 05 13
加密后的： 41 55 46 00 63 90 12 83 15 98 18 18
（注：数字表示+Xn=加密后的）
如果我们不知道 a,b,还有 m是多少!只知道这个公式Xn＋1=aXn +b mod m
并且知道X0=19, 还有加密后的的信息的数字 比如这串数字41 55 46 00 63 90 12 83 15 98 18 18.
现在问题来了假如我们不知道这条信息是什么,但是我们猜到其中一个单词"secret”,并且知道这个单词的位置例如
加密后的： .63 90 12 83 15 98 .
数字表示： . 19 05 03 18 05 20 .
Xn(n≠0) ： . 44 85 09 65 10 78 .
现在的问题就是要通过这里算出a,b,m ,运算方法很简单我也知道步骤
通过公式我们可以得到
85≡44a+b mod m
9 ≡85a+b mod m
65≡9a+b mod m
10≡65a+b mod m
78≡10a+b mod m
通过计算就可以得到a=13,b=35,m=87
这里计算方式可以比较简单,但是如果遇见大的复杂问题可能就比较麻烦
所以我这道题目的问题是如果通过这个
加密后的： .63 90 12 83 15 98 .
数字表示： . 19 05 03 18 05 20 .
Xn(n≠0) ： . 44 85 09 65 10 78 .
怎么看出86≤m≤99? 以减少运算步骤,可以省去不少时间!
还有如果猜到一个更大的单词比如“unnecessary” 那么就要列出10个方程来算出
a,b,m, 是不是一定要列出10个方程?最少只要列出几个就可以算了?
文字比较多,但是类容比较简单,并不复杂!
希望高手可以帮忙!

Answer 1

这是求同余的题目,最好向数学系的同学问问!