|
[原创]整数分解随笔(一个算法)
给你N个球,将其排成方形,长宽各多少个球?这就是RSA因式分解问题。 现在换一个思路,将其排成等腰三角形,第n行排2n-1个球,显然,可能排完第n行后,剩下的球不足排第n+1行。 这时,我们改换策略,将其排成等腰梯形,将等腰三角形前m行追加到第n+1行及后续行,以使最后一行恰好排满,不多不少。 现在我们用表达式来看看这个过程的含义:假设排出的等腰三角形有n行,剩余r个球,那么N=n^2+r(初值为1,步进为2的等差数列求和结果是n^2),假设需要截取三角形前t行刚好将剩余r个球补成梯形,并假设梯形最后一行是第m行,那么m^2=N+t^2,即N=m^2-t^2=(m+t)(m-t)。 这种存在两种“碰运气”的方式:一种是搜索“截取三角形前t行”中的t,一种是搜索“梯形最后一行m”中的m,显然后种方式效率高。 所以,问题可以转化为:给定自然数N,求最小正整数t,使得N+t^2是平方数。 求解方式是,给定N,求出满足a^2<N的最大整数a,遍历判断(a+1)^2-N,(a+2)^2-N,...,找出第一个平方数即可。 当然,上述方法依然是亚指数级的,不足以破解现在普遍使用的RSA。可以考虑使用上述思路,这里只是选取了三角形和梯形,还有很多形状可以考虑,也不限于使用线性递增(等差数列可以看做是线性递增),也不应局限于整数内考虑,只要能找到更快速的遍历方式即可。 |
|
|
|
[讨论]如何度量数组的混乱程度
我用过相关测试软件,也按其标准独立写过随机数测试软件,没有觉得是“垃圾”。 “你就是用常数数组也就是元素都一样的数组去测试,那15项玩意里也有能测试通过的项目”你自己对它都不明不白,妄加评论只会误导他人。 |
|
|
|
[求助]密码学滑动窗口算法
滑动窗口算法的基本思想是,将指数有连续bit“1”的地方,一次性算,而不需要每bit都算。 例如:按从右往左计算S=x^emodM,其中e=10110111。 普通做法是:S赋初值1,从高往低位遍历e,遇到1执行S*=S,S*=x;遇到0执行S*=S。 窗口法(假设窗口宽度3bit):S赋初值1,从高往低观测e中连续“1”的情况,例如第一次观察只有1个“1”,执行S*=S,S*=x,由于第二bit为“0”,执行S*=S;继续执行,发现第3,4bit均为“1”,执行两次S*=S,执行一次S*=x2(x2=x^3是预计算好的值);继续执行,由于第5bit为“0”,执行S*=S;继续执行,发现第6,7,8bit均为“1”,执行三次S*=S,执行一次S*=x3(x2=x^7是预计算好的值)。 滑动窗口法可以提高速度,但是会额外多消耗内存,因为预计算值需要提前计算并存储。窗口越大,需要的预计算值越多。指数bit位小时,相应窗口也不要太大,否则也不能起到提速的作用。 |
|
[原创]随机函数的改造
“这种方式是借助随机函数来挑选数表中的数值” AES的大致流程: 1、使用密钥构造轮密钥,构造轮密钥的过程即相当于你说的随机函数; 2、轮密钥与明文做线性变换(行变换和列变换)作为S盒的输入; 3、使用多项式逆元的一些线性变换构造S盒,S盒即相当于你说的数表; 4、对S盒的输出做行变换和列变换,作为新的明文; 5、重复上述2,3,4若干回合,得出密文。 你的做法需要具体化“随机函数”和“数表”的实现方式,当然,“数表”不够大的话,数表的多次输入输出之间最好还要加一些变换。 其实,现代的对称密码算法的关键就是S盒的设计,也就是你说的“数表”的设计。 而对于随机数,现在一般的生成方式是: 1、用物理随机源(模拟电路)生成随机数; 2、后处理:后处理过程通常类似于AES的第4步。 |
|
|
|
|
|
[原创]myMiniLock公钥加密小工具
其实这个使用sm9更合适。 |
|
|
|
|
|
[求助]关于求Fp上模逆的疑问??
这里使用递归是有风险的,栈消耗与初值相关,难以控制。 |
|
[求助]关于求Fp上模逆的疑问??
可以证明两点: 1、x1与x2符号相反; 2、每次迭代,x1,x2符号均变反。 你给的程序只是计算公式的形式化,转化为C语言时需要做一些处理。简单的做法是添加一个标识x1符号的变量。 1. u = a; v = p; 2. x1 = 1; x2 = 0; flag=0; 3. 当 (u!=1) 时, 重复执行: 3.1 q = v/u, r=v-qu, x = qx1+x2, x2=x1, x1=x; 3.2 v = u, u = r, flag = flag^1; 4 if(flag==0) return x1%p; else return (x1+p)%p; 这个程序可以改造成求最大公约数及其表达系数的程序: x1=1,x2=0,y1=0,y2=1;flag = 0; while(u) { q = v/u; r = v - q*u; m = x2 + q*x1; n = y2 + q*y1; flag = flag^1; v = u; u = r; x2 = x1; x1 = m; y2 = y1; y1 = n; } // ux + vy = d *d = v;// 最大公约数 *x = x2; *y = y2; return flag;//返回x的符号位 |
|
关于C语言中必须要用到指针的讨论
指针是记录对象位置的变量。从计算机语言的功能讲,不是必须的,即使语法上不定义指针,也不影响语言表达功能的正确性。完全可以把普通变量当指针来用,只是这样会有诸多不便,例如: 1、要访问一个对象的成员变量,程序员需要手动计算其相对地址,然后才能找到该变量,对象结构的微小变化,相对地址也会发生变化,从而你的程序需要修改的地方比较多。但如果使用指针,会方便许多,成员变量相对地址的计算,全部由编译器帮你完成,即使对象结构变化,成员变量的寻址在形式上没有变化。 2、函数指针如果使用普通变量,似乎C/C++还真不容易实现。 指针被独立抽象出来,确实可以极大的方便程序员编程。 |
|
[求助]能有哪位大侠给我科普下程序入口点的知识?
首先需要了解何谓“程序”?举几个例子。在windows上,所有的exe、lib、dll等,均是PE格式文件,这些文件就是程序;在Linux下,所有的elf、a等,均是elf格式文件,这些文件也是程序;在单片机上,例如s、bin、hex等也可以是程序。 那么他们都有什么共同点及区别呢? 先说共同点。既然是程序,那么必须包含机器能识别的机器码,也就是经过编译器转化后的代码,当然,也可能会包含一些数据,例如你写的程序中有一些全局对象是有初值的,这些初值,也必须包含在你的程序中。 再说区别。这也是需要重点关注的地方。通常,一个程序只提供机器码及数据,程序加载器就无法知道程序从哪运行,也不知道程序中的资源(例如函数接口或对象)如何访问,所以,“程序”也需要提供一些对代码和数据的控制信息,用来告诉加载器相关信息,当然,这些控制信息是编译器和链接器根据你的指定帮你生成。不同格式的文件,收集的这些控制信息会不同,存储方式也不同。当然,也存在不带任何控制信息的“程序”,例如bin文件,这意味着加载器与bin已经事先商定好程序入口,单片机常常使用这一做法。 现在你的问题自然就得到解答。 程序入口点就是程序被加载到内存中的开始的位置吗?在PE/ELF中,通常不是,程序文本的开始,通常是程序控制信息,在单片机中,可能是,因为没有程序控制信息,那么最简单的协商方式就是默认程序文本的开始位置就是程序入口。当然也可能不是,因为加载器可能是通过中断加载的方式,这时,程序文本的开始,会是一个中断函数入口地址。 main函数和入口点有什么关系呢?通常这是你告诉编译器,main是你的代码入口点。编译器根据你的指定,在程序控制信息中,就会声明main是入口,加载器查询程序控制信息后,就知道跳到main去执行了。 再还有就是在程序中,我想获得本程序的入口点有没有可能?当然有可能,不过需要系统支持。加载器是能够清楚的知道你的每一个函数和变量地址的(只要你在控制信息中声明了这一点),加载器告知告知系统,你的程序通过调用系统的函数,就能找到自己。 |
|
[原创]分组密码的弊病及纠正
加密算法的强度取决于其关键部分的强度,并不是说des上套一层aes,强度就是des*aes。 |
|
|
|
[讨论]关于随机数
用硬件产生随机数种子,用软件(密码算法)产生随机数,这是业界一般做法。 利用系统时钟等做种子,种子空间不够大,一般使用在安全要求不是太高的地方也没有问题。 使用当前电路的电流值做随机种子,电路实现会复杂,至少数字电路实现会比较复杂。 前面介绍的方法,随机性确实部分依赖于初值,但初值是由电子元器件误差及用户人为操作综合决定,使用k*n mod 2这个算法主要是电路实现简单,且放大效果还不错。其实这个问题还是有很多值得研究的地方。例如,把“1米”换成“1米左右”,把“Pi(n)米”换成“Pi(n)米左右”,如果这里的“左右”指正态分布,那么如何该选择n?标记“0”“1”的时候,0,1状态该持续多久才认为是0,1?这些都是比较复杂的问题。 |
操作理由
RANk
{{ user_info.golds == '' ? 0 : user_info.golds }}
雪币
{{ experience }}
课程经验
{{ score }}
学习收益
{{study_duration_fmt}}
学习时长
基本信息
荣誉称号:
{{ honorary_title }}
能力排名:
No.{{ rank_num }}
等 级:
LV{{ rank_lv-100 }}
活跃值:
在线值:
浏览人数:{{ visits }}
最近活跃:{{ last_active_time }}
注册时间:{{ user_info.create_date_jsonfmt }}
勋章
兑换勋章
证书
证书查询 >
能力值