Sagemath | 基于大整数分解的Rabin加密

Sagemath | 基于大整数分解的Rabin加密

问题概述

Sagemath | 基于大整数分解的Rabin加密

分析

使用sagemeth进行**运算,运算过程大约15秒。

首先将N质因数分解成两个素数p,q:
p=990932843298892349238943242791,
q=2387883598789374983927498237627。

再用模幂计算出:
Sagemath | 基于大整数分解的Rabin加密
Sagemath | 基于大整数分解的Rabin加密
可得:
mp=358546986862207226911256688941,
mq=1790411145826943505290886300376;

Sagemath | 基于大整数分解的Rabin加密

欧几里得辗转相除法求出满足sp + tq=1的s、t的值:

s=417850213941792666727100662729;
t=-173401040479659357453257331194。

再用中国剩余定理解得x1,x2,x3,x4:

X1=1180750646513203924856355379026414770979645149607;
X2=2366232284013966098921140426254459982575397735186553227547350
X3=874422063025296895941599983057263334241694752879172800315388
X4=1491810220989849953626053647122053003712729397078360072381569。

Sagemath | 基于大整数分解的Rabin加密

猜想将其转换成16进制看一下是否有进一步的含义,x1,x2,x3,x4转换后的结果如图:
Sagemath | 基于大整数分解的Rabin加密

进一步4个一组,查询编码,看看是否有对应的意义,x1所对应的汉字如下,x2、x3、x4无对应含义:

Sagemath | 基于大整数分解的Rabin加密