00:01
嗯,好,嗯,然后我们看一下这个,嗯嗯,RO思后CTF2019贝VRC这道题啊,它是涉及一个V尔是V尔式定理的这道题。嗯。啊,威尔逊定理,呃,它这个加密脚本啊,也就是他的这个题干啊,题目给的是一个,呃。啊,就是给了一个脚本啊,是啊,有一个这么my get pre,然后这个获取这个字数的一个函数,然后可以看到AA,它是获得一个50,呃,513位的一个质数,然后打印一下A,然后B,然后是减去一个啊随机数后面一个啊1000到这个,嗯,是后面五个零。这是18,嗯。然后呃,打印一下B,然后返回一个,返回一个B的阶乘,嗯,然后呃,对A,呃,再取一个余数啊然后的下一个质数,然后呃,这个可以看到这个呃,PP是一个质数,然后Q是一个质数,然后二也是一个质数,然后NN是三个数,相三个是相乘,然后然后这个C是QW啊一个常见的这个啊铭文,然后呃公钥然加密IC呃这里涉及一个V尔虚定,V尔虚定理就是呃,如果P是速数,P的P减一的结乘等,或者就是嗯。
01:26
啊与啊和这个负一啊,和这个负一啊,他们是这个啊,关于P是同于这样的啊。呃,老师没有学过,呃系统的书论,然后嗯,今天是看到今天是第二第二遍做这道题目,嗯给大家讲一下,然后呃自己的一些呃新的思考啊见解,然后呃这里有一个推导过程,他这个写的就非常详细了啊,我这里呃他这里写的并不是特别特别容易,呃分看清好这里那这里我这里又给大家写了一下,就是B的阶成啊就是。
02:01
呃,对A求余啊,首先我们如果要是如果要是求出来,这求出来这一块就是B的阶乘对A求余,然后那我们再就是自己再算一个next pro,然后这样子就能算出来P和Q了,对吧?啊,所以我们重点是求这个,呃,AB啊,AB是多少啊,也不是说AB是多,AB它告诉你了A是多少,B是多少,但是我们要B的结乘对A求余啊,但是B的数很大,你要是结乘的话,嗯,这样算你肯定是跑不通的,知道。然后呃,我们先去画成这种形式,就是呃,从A减一开始算A减一,A减二,然后一直乘,乘到B加一乘B,再乘到B减一啊,一直到呃到一,然后这里啊分母的话它是呃A减一,然后到B加一啊这样的话,其实上下两项可以约掉,就是我们就是故意添加上了,然后再对于A这样进行一个求与,然后我们可以看到就是呃上面这一块,上面这一块就是A减一的这个,A减一的这个结成,A减一的这这个阶成,然后下面这块就是A减一到B加一,然后这下边。
03:05
然后呃,其实这是涉及一个就是呃,这是我刚学的一个。涉及这个有理式有理分式的曲模运算啊这个链接啊,这个链接简讲的也非常详细,他呃他就是写了一些就是呃取模的基本运算就加B,然后对P求于嗯,然后A减B,呃然后求于PA乘B求以PA,然后A除以PA除以BA,呃去求以BA,而这样是错误的,其实呃这种形式,这这种形式非常非常,虽然非常工整,但是实际上是错误的啊,这里写了一个就是呃。啊,写了一些说明,然后包括他这个证明啊,证明的过程也比较直观,就是呃。就是A除A除以B,然后求于P等于M,比如说M是铭文,然后这里我们就是两边同时乘以一个B,那就是A求于P等于MB乘以求P,然后再同时乘以这个呃,X,这里前提设了这个B的X,呃就是XX是B的这个力源,就是啊,同时磨P的这个情况就是。
04:11
相当于它密密源的话,自然就有这个公式,就是BX等,那就是嗯。呃,一是这个鱼是这个同于的啊,关于P。嗯。所以所以这里划划成这个第三个式子,第三个式子,然后又结合这个式子,然后所以这个BX直接可以写成一,就是啊,这里就是AX,然后呃和M是关于P同于。这里涉,这里就是涉及啊数论,数论这一块的知识,然后呃,然后的话,然后嗯,这里是。这XX我们知道X我们刚才说的就是B的,呃,就是B的那个关于P的这个啊逆源嘛,就是所以就是A乘以B的这个逆源,然后啊就等于一个嗯,M啊跟这个呃和M是同一的。
05:01
所以这里我们就,嗯,所以这里我们就画一下,画一。然后呃,这这一块这一块的话,它就是A减一呃的结成啊对呃就是模模A模A,然后先不管这一块,先看后面这一块,后面这一块的话,然后他就是呃一个叫。嗯,它就是啊这个啊B的逆源也就是X,那就是下面这个下面的就呃下面这这一个的这个逆源,A减一的逆源,然后去呃磨AA减二的力源去磨A,然后A到B加一的力源去磨A,然后再去再去磨A磨AA这样。嗯,然后前面这一块,前面这一块这是这是中间是一个乘法,然后前面这一块的话,呃呃,因为我们知道A是质数,就是就是看到这里题题目他给给你了,就是题目这里a get,呃,Get5135.10 513位一个质数,这点C厘面,然后所以可以这这不可以直接画,这不可以直接画成这个pow就是负一的一次方,就是再去求于A,呃,这这里的话就是负一的一次方求于A,呃跟我们常常见高中的那种它是不一样的,就。
06:16
我们可以去输出一下,比如说就是输出这个pow,呃,Mod是一样的道理,跟那个pow是一样的,呃只不过是是GMPY2这个库里面这样去打印一下,打印一下的话可以发现就是两个值,因为呃,因为我这里呃要调用这个函数,调用两次。可以发现这个AA这个呢,就是它都是减一位,就是呃零七,然后这里是二七,所以这里是0626。呃,是一个同学的关系。呃,对,就是最好不要想,最好不要,呃就是拿高中的,呃一些常见的这个思维,思维就是啊一啊我去求于一负,负一我去求一个,呃求一个大A啊,我不知道怎么呃怎么求啊,因为它是一个牵扯到一个正号。
07:08
呃,然后所以呃,所以这个数还是比较大的这个数,呃,然后我们最后得到的就是呃,TMPTMP去乘以,乘以这个啊,乘以这个NS乘以这个。呃。那然后这块其实还是有一个括号的。啊,这一个大花。呃,然后呃,这里的话就是一个啊这个啊这个有理啊,啊这个有理有理分式啊,有理分式的情况预算。然后GM p2啊,这里就是就是去求它的这个嗯,I是从B加一啊,这里也写了B加一到这个A啊到这A减一啊当然这块Python么就是呃就是实际上是导A减一,然后呃去呃求一个逆元啊求一个逆源,求一个逆源,然后呃就是模模的呃第二个呃这个呃这个函数va的这个函数采用第一个参数啊第一个参数呃第二个参数就是这个模。
08:05
我当然就是选A这里,然后呃,I的话,然后就是从这个B加一到A到A这里。啊到A点一这里,然后呃把它们都相乘起来,因为它还是乘,呃还是乘法,就是啊相乘起来,乘起来之后啊,这个NN我们可以设为一,然后刚开始数值,然后这样子,呃是一个呃累计相累积相乘,然后呃,当然我们还呃还需要就是不断的去这个求余,这A对对A求一个余数啊。啊,这呃,然后最后我们再return return返回这个,返回这两个数的相乘,然后再去,就因为呃。呃,这样呢,我们就去得到了一个,呃。这样我们就去得到一个这个啊,BB的截乘求于ABB的截乘求A,然后我们再去呃去呃,就是调用这个啊,就是它的下一个质数啊,得到这个,得到这个一呃得到这个不一定它是一个质数,就是我们直接去求它下一个质数。
09:03
下一个就是。这个库的话,我们就是可以去演示一下。我先放木了,我说话。啊,我这里求一个5555可能话它是一个合数啊,它不是质数啊,然后它下一个质数就是啊啊五九啊,你比如说5656,它可能不是,然后5757的话有谁,然后啊五八可能就说五七的话,比如说是嗯。
10:13
咦,什么?五七肯定333可以,三是它的一个因数,三三九二十七嘛,对五七肯定也行,所以他下一个就是五九哦,五九就是只有只有一乘五十九一和他的身这样。嗯,然后呃,下面就比较常规的就是N去求一个这个,呃算一个P,然后再去求一个力源,然后呃,常规的一个就是IC的一个解题思路啊,主要是前面啊涉及一个V尔逊经理,包括这个式子的转化,嗯。然后这是这道题目的一个啊,就是简单的一个分享。
我来说两句