符号含义与适用前提 二次域的基本结论 x2- dy2= ±1 x2+ y2= n 参考文献 [1] 代数与数论 李超 周悦春秋十二月2024-12-23 11:33发表评论 ...继续阅读 (19)

原本算法 摘抄参考文献1中附录的算法流程如下 例子测验 改正后的算法 改正之前，先理清原本算法判别不可约多项式所用的原理。其原理是若f(x)可约，当且仅当存在次数i<=d=[deg(f(x))/2]的不可约因子g(x)，而此时gcd(xq^i-x, f(x))≠1。 根据参考文献2（详见如下定理），xq^i-x是所有i次不可约多项式的乘积，因此它必定包含g(x)而与f(x)存在公因子。不可约判别算法的思想应该是遍历次数1到d的所有不可约多项式 （没必要检测大于d的不可约多项式，因为若f(x)可约则其分解因子中必定存在不大于d的不可约多项式），检测输入多项式与它们是否存在公因子。所以这个原理是正确的，只是实现不对， 略作改正如下（类c语言描述） 重新测验 参考文献 [1] 算法数论 裴定一、祝跃飞 [2] 代数学基础与有限域 林东岱春秋十二月2024-09-07 23:07发表评论 ...继续阅读 (35)

通用算法 先摘抄参考文献[1]中的算法流程如下 正确性分析 下面证明以上算法用到的事实结论，提炼为如下几个引理 算法构造思想 用到二次剩余知识，即一个待求平方元ɑ可以且只能表示为两个平方因子的乘积，其中一因子为任意随机选取的非平方因子β的偶数幂， 另一因子为叶子群H的一元素r，H作为陪集划分根群（有限域乘法群）得到β生成的集合即商群G/H的一个代表元系。这样一来，将开方转化为β与r的乘方运算， 迭代的过程就是为求那个具体的代表元βe中的指数e（注意e必为偶数），从Gs-2到G0=H，迭代结束后r被唯一确定，r的开方等于r的(t+1)/2次方（因为t是H的阶且为奇数，rt+1=r） 例子测验 特殊算法 当q是素数且q≡3(mod 4)时，存在更快的算法及测验如下 参考文献 [1] 算法数论 裴定一、祝跃飞春秋十二月2024-08-30 22:22发表评论 ...继续阅读 (53)

基本原理 再来看Terr算法用到的如下定理 定理（基于参考文献1改正后的描述）对每一正整数t，存在唯一确定的一组整数k和j，0<=k=1 如果t=0，则j在区间[0,1)，故只能取0，此时k=0与条件kj=1, k=0 t=2 => j=2, k=1 t=3 => j=2, k=0 t=4 => j=3, k=2 t=5 => j=3, k=1 t=6 => j=3, k=0 算法伪代码 例子测验 参考文献 [1] 代数学基础与有限域 林东岱春秋十二月2024-08-15 22:35发表评论 ...继续阅读 (99)

私钥分组加密 上图的证明中，r(j)两两不同的概率计算是关键，下面给出详细过程 另外两个分布统计的不同意味着计算可分辨（反之则计算不可分辨），亦即r(j)至少两个相同的概率私密通用加密 安全性分析 春秋十二月2024-06-29 17:00发表评论 ...继续阅读 (41)

定义 Berlekamp分解算法 AES有限域 不可约性证明 非本原性验证 找出本原元 不可约多项式个数 线性移位寄存器m序列 根据参考文献1知线生移位寄存器产生m序列的充要条件是特征多项式f(x)为本原多项式。而确立有限域上的本原多项式，主要有两种方法： 一种方法是根据Fq上所有次数为n的本原多项式的乘积正好等于割圆多项式Qe，其中e=qn-1，从而所有次数为n的本原多项式可以通过分解Qe得到。 另一种方法是通过构造本原元再求本原元的极小多项式，先素因子分解qn-1=p1p2...pk，如果对每一pi都有ord(αi)=pi，那么α=α1α2...αk的阶就是qn-1， 因此是Fq上的本原元，则f(x)=(x-α)(x-α2)...(x-αr)，r=qn-1（因为α是本原元，所以n是使αq^n=α成立的最小正整数）。 求解本原多项式 假设线性移位寄存器的级数为4，这里使用上述第二种方法求F16上的本原多项式，过程如下 本原多项式个数 m序列示例 参考文献 ...继续阅读 (62)

管理->选项->Configure 的 首页HTML代码中写入Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/应该是某位大佬加了https证书后忘记将页面内的css样式链接改成https了, 导致该资源被浏览器拦截Khan2024-04-30 16:54发表评论 ...继续阅读 (52)

【适用前提】大整数N=pq的素因子p<2p，解密指数d<(1/3)N1/4【攻击方法】 1）用欧几里得算法计算e/N的各个渐近分数ki/di，直至di<(1/3)N1/4。令i=1 2）计算T=(e*di-1)/ki，若T不为整数则结束返回，否则转到3） 3）计算一元二次方程f(x)=x2-(N-T+1)x+N=0的根，如果有根且两个根皆为小于N的正整数，则输出p、q；否则递增i，转回2） 该方法即Wiener算法用到了关于连分数的一个定理：若α为任一实数，有理数p/q适合|α-(p/q)|<1/(2q2)，则p/q必为α的某一渐近分数。证明详见参考文献[2]。 由定理可知攻击方法是收敛的，必能找到使f(x)=0有合理解的某渐近分数。下面证明：攻击迭代次数的上界为【证明】 【例子】N = 9449868410449，e = 6792605526025，d<(1/3)N1/4≈584，试分解N 参考文献 [1] 公钥密码学的数学基础 王小云、王明强、孟宪萌 [2] 算法数论 裴定一、祝跃飞春秋十二月2024-04-04 18:19发表评论 ...继续阅读 (77)

混合线性同余发生器（MLCG） Xn≡ αXn-1+ c mod m 02，如果 x=1(mod pα)，x≠1(mod pα+1)；则xp=1(mod pα+1)， xp≠1(mod pα+2) 本文主要阐述为什么p是使xp=1(mod pα+1)成立的最小正整数，以及一般情形m=pw(w≥1)是使xm=1(mod pα+w)成立的最小正整数 ◆ 先论证不存在一个整数1≤b ...继续阅读 (64)

【定义】设整数N=P×Q，P与Q皆为素数，如果P≡Q≡3 (mod4)，则N为一个Blum（布卢姆）数【定理】设N为Blum数，N ∤ d，若同余方程x2≡d (mod N)有解，则d的平方根中有一半的Jacobi符号为1，另一半Jacobi符号为-1；且仅有一个平方根为模N的二次剩余 【推论】设N为Blum数，N=P*Q，令 证明： 【应用】Blum-Goldwasser公钥加密 解密正确性是因为步骤1用到了欧拉定理及求平方根的如下算法，步骤2用到了中国剩余定理 从上可得x=s(P+1)/4mod P或x=P-s(P+1)/4mod P，因(-1)(P-1)/2等于-1 mod P，故前者为模P的二次剩余。 所以从密文中r求它的(p+1)/4次幂、(q+1)/4次幂，迭代n次就得到了s1模p的解、s1模q的解，又因p、q、n在迭代中不变，故用欧拉定理预计算dpmod (p-1)、dqmod (q-1)春秋十二月2024-02-25 23:29发表评论 ...继续阅读 (75)

经典的复杂性关系 P是多项式时间确定型图灵机可识别的语言类，NP是多项式时间非确定型图灵机可识别的语言类，NPC表示NP完全问题类，coNP表示NP的补，coNPC表示NPC的补。确定型图灵机是一种从不选择移动的特殊的非确定型图灵机，故自然有P属于NP coNP、coNPC的定义之集合表述 上面顶部的图有个假设前提是：coNPC不属于NP，即我们相信NP完全问题的补都不属于NP。但当P=NP或NP=coNP时，可以发现coNPC属于NP ◆ 为什么coNPC属于coNP？ ◆ 为什么NPC 不属于coNP？ ◆ 为什么P属于coNP? ◆ 当P=NP时，为什么NP=coNP？ ◆ 当NP=coNP时，为什么NPC=coNPC？ 前文的关系演变图没考虑多项式空间问题类PS与递归问题类（因为那两个条件不会影响到它们），PS（NPS）是带多项式空间限制的确定型（非确定型）图灵机可接受的语言类，但不限制运行时间可能需超多项式或指数时间，在外围加上PS与递归语言类后如下 ◆ 为什么coNP 属于PS？ 零知识复杂性关系 BPP是可被概率多项式时间图灵机(即随机化算法)识别的语言类，IP是所有具有交互证明系统的语言构成的类，等于多项式空间语言类即前文经典复杂性关系中的 ...继续阅读 (76)

OpenCASCADE HLR Quadric Surface Outline EdgeKey Words: HLR, Outline Edge, Sihouette Edge1 IntroductionOpenCASCADE中关于隐藏线消除HLR算法的描述就是一句话：These algorithms are based on the principle of comparing each edge of the shape to be visualized with each of its faces, and calculating the visible and the hidden parts of each edge. 即根据面判断每条边Edge的遮挡关系，计算出边Edge可见和不可见部分。所以HLR算法的输入主要为边和面，计算遮挡关系依赖线面求交算法。对于精确的HLR算法依赖精确的线面求交算法，PolyAlgo算法依赖多段线与网格求交算法。输入的边中除了BREP中的边以外，还有一类是根据投影方向计算得来的，即外轮廓线Outline，也称为Contour线。ACIS的PHLR中称轮廓线Sihouette Edge。轮廓线的计算是HLR中比较关键的一步，本文以OpenCASCADE中简单的二次曲面的轮廓线计算入手来理解曲面的轮廓线概念，为理解任意曲面轮廓线计算打下基础。2 ...继续阅读 (88)

OpenCASCADE-HLR Edge1 Introduction用计算机生成三维物体的真实图形，是计算机图形学研究的重要内容。真实图形在仿真模拟、几何造型、广告影视和科学计算可视化等许多领域都有着广泛应用。在用显示设备描述物体的图形时，必须把三维信息经过某种投影变换在二维的显示平面上绘制出来。从三维投影到二维的降维操作，会导致图形的二义性。要消除这类二义性，就必须在绘制时消除被遮挡的不可见的线或面，习惯上称之为消除隐藏线Hidden Line Removal和隐藏面Hidden Face Removal。这是渲染显示上对消隐的需求，在根据三维模型自动生成工程图的工程设计软件中，对消隐的需求有所不同。工程设计软件与机械设计软件不同，工程设计软件一次出图消隐的模型量大，对出图的算法要求主要有：主要使用消隐线算法；消隐得到的线能找到与三维模型的关系，方便标注模型信息，如模型名称、规格等；自动标注布局算法，能对标注的名称、规格等自动布局，减少手工调整；自动尺寸标注；符号化处理，如管道模型能用一条线符号化处理；其实最后总结成一句话就是一键根据模型生成能交付的图纸。虽然现在技术上具备三维模型下车间的能力，但是目前二维图纸依然是设计交付、加工制造主要依据。工程类设计软件主要的功能就是快速建模，碰撞检测和自动图纸生成。当模型量大时，消隐速度快及自动生成的标注文字排列整齐（或满足工程习惯）成了二 ...继续阅读 (90)

OpenCASCADE 线面求交eryar@163.com1 IntroductionOpenCASCADE中几何曲线与曲面求交使用类GeomAPI_IntCS，是对类IntCurveSurface_HInter的简单封装。在IntCurveSurface_HInter中对曲线和曲面求交分为以下几种类型：PerformConicSurf：二次曲线与曲面求交，其中又分为两类：二次曲线与二次曲面求交和二次曲线和自由曲面求交；InternalPerformCurveQuadric：自由曲线与二次曲面求交；InternalPerform：自由曲线和自由曲面求交；本文主要介绍曲线与曲面求交的实现原理。2 二次曲线与二次曲面求交二次曲线与二次曲面求交使用IntAna_ConicQuad计算，主要思路是将曲线用参数方程表示，代入二次曲面的代数方程。二次曲面可以使用二次多项式表示，将二次曲线与二次曲面相交表示成一个多项式方程，使用math_DirectPolynomialRoots对多项式方程进行求解。3 二次曲线与自由曲面求交二次曲线与自由曲面求交将曲面使用IntCurveSurface_Polyhedron在U，V上采样离散得到grid网格。这个类实现与IntPolyh_MaillageAffinage类功能有重复。IntCurveSurface_ThePolygon多段线与Intf_Inte ...继续阅读 (89)

OpenCASCADE二维曲线求交1 IntroductionOpenCASCADE中对二维曲线求交和三维曲线求交是不同的，三维曲线求交统一使用离散法，二维曲线求交根据曲线类型的不同分种类型进行处理。二维曲线求交中还提供了计算自交的直接接口。在TKGeomAlgo中，主要内容就是拟合、求交算法，理解求交算法的实现原理，达到能阅读和修改源码的状态，能够分析和解决实际遇到的问题，理解OpenCASCADE的能力边界，根据需要选择所需要的功能，使软件结果可控。本文主要介绍二维曲线相交的实现原理。由于OpenCASCADE开发时间相对久远，在二维曲线求交相关代码中大量使用了宏定义的方式来实现C++ 的模板template能力，宏定义在类的XXX_0.cxx文件中，对应模板实现在*.gxx中：这种实现方式会让代码的可读性变差，不利于代码维护。应该用C++的方式对这些*.gxx代码重构，增强代码可读性和可维护性。2 求交分类二维求交使用类Geom2dAPI_InterCurveCurve， 这个类是对类Geom2dInt_GInter的封装。在类Geom2dInt_GInter中，如果只输入一条曲线，可以计算自交，如果输入两条曲线，计算两条曲线的相交。IntCurve_IntConicConic：二次曲线与二次曲线求交。二次曲线与二次曲线求交都先使用几何方法计算交点，再判断是否在参数范围内；G ...继续阅读 (82)

OpenCASCADE曲线上点的反求eryar@163.com1 Introduction曲线可以用代数方程表示，如圆可以用X^2+Y^2=R^2表示，也可以用参数方程X(u)=RCos(u), Y(u)=RSin(u)表示。要判断点是不是在线上，用曲线代数方程可以很直接得出结果，但是使用参数方程就没有那么直接。这也是参数曲线上点的反求问题，参数曲线上点的反求问题应用广泛，如前面所述判断点是否在曲线上、点向曲线投影、点与线的求交、点在参数曲线上的参数等，都与点的反求问题相关。本文主要结合代码介绍OpenCASCADE曲线上点的反求实现原理及使用过程中的一些注意事项。2 实现原理在《The NURBS Book》书中将点的反求问题归结为点向曲线投影距离最短的问题，如下图所示：建立函数f(u)=C’(u).(C(u) - P)表示点到曲线距离，当f(u)=0时为点到曲线的最短距离，不管点P是否在曲线上。几何意义是点到曲线任意点的向量与任意点处的切向量点积为零，表示在两个向量垂直的时候求得极值点。注意数学方程中垂直这个几何意义。OpenCASCADE中实现曲线上点的反求原理与《The NURBS Book》书中一致。点的反求使用类GeomLib_Tool::Parameter()函数：输入曲线、点和最大距离，计算点是否在曲线上及若在曲线上，点对应参数曲线的参数U。类Extre ...继续阅读 (83)

OpenCASCADE - 曲线自交1 IntroductionOpenCASCADE为二维曲线提供了求交及自交的类 Geom2dAPI_InterCurveCurve：当传入一个二维几何曲线时可以计算自交self-intersections。但是没有提供直接的三维几何曲线求交的类，也没有直接的计算自交的类。有人同学问OpenCASCADE有没有三维曲线自交的功能，其实理解两个Edge求交算法后，可以自己实现一个自交函数。2 Self-Intersection因为OpenCASCADE中两条三维曲线求交的类是IntTools_EdgeEdge，其实现原理是基于包围盒的分割法。基于这个分割递归思想，实现自交也可以参考这个思路。算法的流程为：输入一条要计算自交的边Edge，对边进行离散采样，将采样得到的每段曲线的包围盒生成BVH进行相交检测，将BVH中包围盒相交的两条曲线调用IntTools_EdgeEdge来计算相交。离散得到的曲线段会比较多，如果用两个循环来检测两两曲线段的相交情况性能差，可以引入BVH提高性能。3 Test可以通过插值Interpolate来构造曲线测试，指定几个自交点来构造插值曲线。计算结果如下图所示：与曲线求交原理类似，都是使用离散的方法，可以思考一下数值算法如何处理。eryar2023-12-02 12:21发表评论 ...继续阅读 (82)

OpenCASCADE 曲线求交eryar@163.com1 IntroductionOpenCASCADE中提供了二维几何曲线的求交类Geom2dAPI_InterCurveCurve，对应到三维几何只提供了GeomAPI_IntCS, GeomAPI_IntSS，没有提供几何的GeomAPI_IntCC求交类。这些几何求交一般使用的是数值算法，即解方程。对于两条几何曲线P(u1), Q(u2)，求交就是解P(u1) - Q(u2) = 0这个方程。为什么对于三维几何曲线没有提供数值算法？对于拓朴边提供了求交算法IntTools_EdgeEdge，这个类是使用类似于曲面求交的离散网格法，使用了离散包围盒法。基于包围合盒的算法是个递归算法，算法思路：1) 检查两条边在参数范围内的包围盒，若空间干涉，则进行下一步；否则退出本次判断；2) 找出两条边包围盒的公共部分对应的参数，若没找到，则退出本次判断；3) 并将第一条边在参数范围内分割成2或3部分，执行第一步；4) 退出条件：没有相交或找到相交的参数值；第一次是分别分成2部分：在递归函数FindSolutions()中，只去对第一条边进行参数分割成3部分：2 辅助函数第一个辅助函数是FindParameters()，用来更新第二条边在第一条边的的包围盒中的参数范围，使用这个参数范围更新包围盒。第二个辅助函数是CheckCoincide ...继续阅读 (94)

学而不思则罔，思而不学则殆。光看书籍的理论知识，没有实践看不到效果。光看occ的源码，没有理论支撑，不能抓住几何问题的本质。除了在OpenCASCADE入门指南中推荐的书籍之外，还有一些进阶的书籍，放在那儿有时间就看看，总会有些收获。悟性不足，只有勤能补拙。对于看不懂的，只能用“书读百遍，其义自见”安慰一下自己。王元 数学大辞典 工具书 方便一些定义，公式，定理的查找。《计算机辅助几何设计导论》比较全面地介绍了计算机辅助几何设计的发展历史及其主要内容和最新进展，包括现代的T样条曲线曲面。《样条函数与计算几何》叙述样条函数和计算几何的基本理论和方法，同时，总结了作者几年来在该领域中的研究成果.《现代数学基础丛书165：散乱数据拟合的模型、方法和理论（第二版）》介绍了多元散乱数据拟合的一般方法，包括多元散乱数据多项式插值、基于三角剖分的插值方法、Boole和与Loons曲面、Sibson方法或自然邻近法、Shepard方法、Kriging方法、薄板样条方法、MQ拟插值法、径向基函数方法、运动*小二乘法、隐函数样条方法、R函数法等。同时还特别介绍了近年来国际上越来越热并在无网格微分方程数值解方面有诸多应用的径向基函数方法及其相关理论。主要内容包括几何偏微分方程的构造方法、各种微分几何算子的离散化方法及其离散格式的收敛性、几何偏微分方程数值求解的有限差分法、有限 ...继续阅读 (101)

周知内联是为了消除函数调用的代价，即四大指令序列：调用前序列、被调者起始序列、被调者收尾序列、返回后序列。它们通常对应到体系结构调用者保存/恢复寄存器集合与被调者保存/恢复寄存器集合之约束。这个本质也是内联的前提。试问如果有某体系结构比如S，它任意深度的函数调用代价几乎为零，那么显然内联是没意义没必要的。但是S可能存在吗？我认为不太可能。因为机器的资源比如寄存器集数量与堆栈空间是有限的，且调用需要知晓上下文，所以不能够支持任意深度的调用，但是可以支持有限深度比如4层调用，这4层调用代价几乎为零，假设再来一层，那么第5层调用代价就不为零了，这时如果内联第5层就变成4层调用，代价又几乎为零。综上所述，内联无论在何种体系结构，即使在一定深度内没意义也不会破坏性能。体系结构直接影响程序性能。主要体现在指令集、寄存器、cache三块。它们对于编译器实现代码优化必须都考虑，尤其cache比如内联优化、循环展开、基本块布局、函数重排，如果不是因为有cache这玩意，内联优化的复杂性会大为降低，因为不用考虑代码膨胀引起的副作用即cache缺失，只要评估函数的指令数与动态执行消耗的关系，指令数很少但执行耗费很多时钟周期的，则不宜内联，尤其函数为非叶子结点；指令数很多但执行耗费较少的，则可仅内联其中的快速路径代码。因现实存在cache这玩意，就必须权衡代码膨胀带来的副作用，是否能接受一定的膨胀，需要精 ...继续阅读 (82)

谈两个问题：高性能与安全性先谈高性能：这里指代码实现层面（非数学优化层面），使用寄存器优化，即主密钥/轮密钥、敏感数据比如中间/临时变量必须存于寄存器，明文/密文放在内存（若有够用的寄存器则放寄存器），主密钥用特权寄存器（为支持长期存储，比如调试寄存器、MSR寄存器），轮密钥和敏感数据用通用寄存器。那么怎么做？稳妥快捷的方法是用汇编或内联汇编，手工编排寄存器即构建密钥与敏感数据到寄存器集合的映射。如果用高级语言比如c/c++开发，问题在于register关键字非强制生效，即使强制的，编译器优化（比如公共子表达式消除）产生的中间变量及寄存器分配策略不完全可控，需要修改编译器比如llvm强制某些变量必须分配(特定的)寄存器，为通用性要从编程语言语法属性到cpu后端都改动支持，这个方法实现成本有点大再谈安全性：为保障安全就复杂了，由于密钥及敏感数据存于寄存器，首先要防止寄存器交换/拷贝到内存（为避免读取内存的冷启动攻击、基于cache的侧信道攻击）的一切可能因素，比如进程调度、由信号或异步中断引起的处理器模式切换、系统休眠，如果在用户态实现加解密，就避免不了被调度或切换，因为单核上不可能只运行加解密进程，所以得实现在内核态。这样一来就要在加解密中禁止抢占与中断，考虑到系统响应，禁止的粒度不能过大最小为一个分组，分组加解密前禁止抢占与中断（比如调用linux内核接口preempt_disa ...继续阅读 (78)

​1. 区间图：用于局部寄存器分配，基本块内的每个活跃范围看作一个区间（最早定义位置+最新使用位置），所有活跃范围构成区间图。区间图是一种不精确的冲突图（因为高估了活跃范围的范围而导致伪冲突，比如认为一个复制操作连接的或两个源相同目标不同的复制操作产生重叠的两个活跃范围冲突，但实际没有冲突），优势在于着色是P（复杂度O(|V|)或O(|E|)）而非NP问题。llvm早期的线性扫描分配器是基于区间图在全局的扩展，比较适用于JIT编译（减少编译时间）​2. 一般图：用于全局寄存器分配，是一种精确的冲突图（由一组定义与一组使用构成的网络）。优势在于努力最小化溢出活跃范围而生成高效执行的代码，但会牺牲编译时间。llvm的greedy寄存器分配是基于一般图的代表。编译器使用的冲突图可能会将机器约束条件比如多寄存器值/调用约定编码进去而存在重复边，导致不满足图论中的简单图定义，故这里采用一般图​3. 弦图：基于静态单赋值形式名建立的冲突图是弦图。优势在于可以做到最佳着色（复杂度O(|V|+|E|)）而非启发式（基于一般图的全局寄存器分配使用启发式），利于减少寄存器压力。劣势在于必须将指派寄存器后的仍然为静态单赋值代码转换为机器码，而这种转换可能增加寄存器压力，以及插入一些可能非必要的复制操作，若复制操作实现的数据流与ssa phi函数对应，则分配器无法合并这 ...继续阅读 (96)

有单向、双向、三向3种认证方式，前两者必须检查时间戳以防重放攻击，单向因为只有一个消息传递，如果仅靠一次性随机数是无法判断消息是否重放。双向有两个消息传递，一来一回，仅靠一次性随机数只能检测到发响应那方的重放。最后者则不必，可仅通过一次性随机数检测自己是否遭遇重放攻击，因为接收第二个消息的那方，通过判断第二个消息中随机数是否等于自己先前已发送第一个消息中的那个，若不等于则为重放，若等于则发第三个确认消息给对方，对方收到并判断确认消息中的随机数是否等于先前它已发送第二个消息中的随机数，若等于则说明第它收到的第一个消息的确是另一方发送的即非重放，否则为重放。因此三向认证可不必同步双方时钟。但正因为不强制检查时间戳而可能导致中间人攻击：假设通信双方为A、B，中间人为C，攻击步骤如下 1. C与B认证时，发送先前已截获的A到B请求消息给B 2. 截获并存储B到A的响应消息x，但不转发，开始与A认证 3. 收到A的请求消息后，解密x取出其中的随机数Rb作为响应给A消息中的随机数，用自己私钥签署整个消息后发给A 4. 收到并转发A的确认消息给B以上完成后，C就能冒充A与B通信了。一种简单的改进方法是先用对方的公钥加密消息中的随机数，再用自己的私钥签署整个消息。关于网络协议的安全性分析，主流方法是形式化分析，可以借助相关工具来验证找出漏洞春秋十二月2023-09-30 08:00发表评论 ...继续阅读 (107)

1.对于rsa，给定大整数n分解的一对素因子p和q，p或q是否素数决定不了rsa的安全性，但决定rsa算法的正确性，也就是说p或q不能为合数，而安全性取决于n的位数及p、q的距离，因为素数测试是一个P问题，而因子分解是一个NP问题，其耗时是关于n的指数2.对于dh密钥交换，通常选择阶为素数的有限循环(子)群，这时素数决定了安全性。因素数不能再因子分解，故避免了针对阶为合数的质因子分解且利用中国剩余定理求离散对数的(已知最好)攻击3. 周知Shamir门限方案基于多项式的拉格朗日插值公式，普遍的设计采用GF(q)域上的多项式，秘密s为f(0)，q是一个大于n的大素数（n是s被分成的部分数）。正常来讲，参与者个数必须至少是设计时的k，才能恢复出正确的s。如果个数少于k比如k-1，则只能猜测s0=f(0)以构建第k个方程，那么恢复得到的多项式g(x)等同设计时的多项式f(x)的概率是1/q。因为g(x)的项系数可以看作关于s0的同余式即h(s0)=(a+b*s0)mod q的形式，因q为素数，故依模剩余系遍历定理，当s0取GF(q)一值时，则h(s0)唯一对应另一值。所以h(s0)等于f(0)的概率为1/q。由此可见，当q取80位以上，敌手攻击概率不大于1/2^80，这已经很低了。这种门限方案如同RSA加密，再次佐证了素数越大安全性越高4. PGP是密码学经典应用，体现在首先支持保密与认 ...继续阅读 (89)

布尔数据 边的相交eryar@163.com1 Introduction在OpenCASCADE中对于边的相交分为三类：边与点，边与边，边与面，边与点的相交已经归结为点与边的相交处理了，边的相交主要处理边与边，边与面的相交。边与边、边与面的相交会引入一个新的数据结构-公共部分Common Part，用于保存重叠的公共部分数据。2 Edge/Edge Interferences对于两条边的相交是指在两条边的某些地方的距离小于边的容差之和，主要分为两种情况，一种是两条边只有一个交点的情况；一种是有重叠部分的情况；先看只有一个交点情况：我们在DRAW中通过脚本构造最简单的情况来测试。在处理边与边相交的函数BOPAlgo_PaveFiller::PerformEE()中，对每两条边调用BOPAlgo_EdgeEdge进行求交。从这里可以看到Pave Block的使用，相当于对每两条边上的每对Pave Block部分进行求交。这里有一些优化空间，目前是使用的两个循环处理，可以尝试使用BVH来提升一些性能。当每对Pave Block对应的点的索引号一致时，即每对Pave Block的端点重叠时，使用快速计算的算法来判断是否有重叠。对于边的求交结果保存到BOPDS_InterfEE中，都会保存是哪两条边相交及相交的公共部分。对于相交于一点的公共部分的类型为TopAbs_VERTEX，对于有重叠部 ...继续阅读 (119)

布尔数据 BOPDS_Iteratoreryar@163.com1 IntroductionOpenCASCADE中新的布尔工具TKBO相对已经废弃的TKBool代码更规范，更易于理解。与ModelingData和ModelingAlgorithms大的模块组织一样，主要也是数据结构Data Structure+算法Algorithm的组织形式。其中BOPDS为布尔中的数据结构部分，BOPAlgo为布尔中的算法部分。理解算法的前提是先理解数据结构DS(Data Structure)，所以先从数据结构入手，来深入理解布尔操作。本文先从简单的数据结构BOPDS_Iterator开始对源码进行分析。 2 BOPDS_Iterator从类的注释可以看出，迭代器BOPDS_Iterator有以下两个功能：- 找出包围盒相交的Shape；- 遍历相交的一对Shape；//! The class BOPDS_Iterator is //! 1.to compute intersections between BRep sub-shapes //! of arguments of an operation (see the class BOPDS_DS) //! in terms of theirs bounding boxes //! 2.provides interface to iterat ...继续阅读 (98)

近期朋友问到监控，使我探究了kretprobe的实现，想到编译中的尾调用优化，作个小结​1. kretprobe_trampoline_holder该跳转函数无参是必须的或说最好的通用设计，因为替换返回地址是非正常程序流程，即被探测函数的调用者无感知，不存在为跳转函数准备入参。若要设计传参且只读，则不会破坏被探测函数调用者的上下文，但跳转函数内部流程怎么用参数是个问题，这需要一种约定​2. 跳转函数为调用trampoline_handler准备入参，即在栈上构造一个（不完整的）pt_regs，再把它地址即栈顶赋给rdi，rdi是x86_64上传入第一参数使用的寄存器，同时预留一个栈单元存放原返回地址（为什么要预留？因为被探测函数返回时，其调用者存放返回地址的栈空间被释放了，所以得在跳转函数内造一个）。由于trampoline_handler内调到用户自定义handler而传入pt_regs，因此自定义handler内要注意最好别改动pt_regs，否则会破坏被探测函数调用者的上下文​3. 表面看kretprobe的实现流程有点像尾调用优化，但有本质区别。后者中被调尾函数直接释放父调用者的栈帧，就可恢复到父调用者的返回地址；前者不能这样干，因为被探测函数的返回地址被替换了，所以需要一个时地（时机地点）恢复，而这时地正是跳转函数的收尾序列代码，把原来 ...继续阅读 (90)

有理数域的本原多项式与有限域的本原多项式定义不同，前者不要求不可约（由高斯引理知两个本原多项式的乘积还是本原），后者则必须不可约（确保生成的有限域其每个元素有逆元）。aes基于有限域F{0,1}设计，故使用的模8次多项式不可约P(x)=x^8+x^4+x^3+x+1，但不是本原多项式，因为它的阶是51而非255。有限域次数为8的本原多项式有16个、不可约多项式有30个（由莫比乌斯反演推出），具体多项式影响s盒与列混合操作的实现。不可约加之0的逆元规定为0，保证正确加解密。若0的逆元规定为非0比如x，则导致x有两个逆元，便违反了逆元唯一性，除非s盒不用有限域设计。逆元等于其自身的非0元素只有1，原因可类比模素数二次剩余的求解春秋十二月2023-09-13 02:00发表评论 ...继续阅读 (104)

1. 若DFA D是用子集构造法从NFA N构造出来的，则L(D)=L(N)2. 一个语言L被某个DFA接受，当且仅当被某个NFA接受3. 一个语言L被某个£-NFA接受，当且仅当被某个DFA接受4. 若对于某个DFA A，L=L(A)，则存在一个正则表达式R使得L=L(R)5. 每一个用正则表达式定义的语言也可用有穷自动机定义6. 若通过填表算法不能区分两个状态，则它们是等价的7. DFA的状态等价性是传递的8. 若对于DFA每个状态q及与q等价的所有状态组成块，则不同的状态块形成状态集合的划分。也就是说，每个状态恰好属于一个块，同一块中的所有成员都是等价的，从不同块中选择的状态对都不是等价的9. 根据等价状态划分算法最小化DFA D得到的DFA M是唯一的。也就是说，不存在其它等价于D的DFA N，其状态数比M少10. 对于正则表达式，空集是并运算的单位元、连接运算的零元，空串是连接运算的单位元11. 若L和M都是正则语言，则L和M的并、交、差也是12. 若L是字母表T上的正则语言，则~L=T*—L也是13. 若L是正则语言，则L的反转也是14. 若L是字母表T上的正则语言，h是T上的一个同态，则h(L)也是正则的15. 若h是字母表A到字母表T的同态，且L是T上的正则语言，则逆同态h^-1(L)也是正则的春秋十二月2023-09-09 08:11发表评论 ...继续阅读 (95)

因为一个整数p，若检测为合数，这永远是真命题；而检测为素数，这命题只以较大概率成立。 可构造一种NP检测算法，步骤如下：1. 猜测p（位长度n）的因子列表｛p1,p2,…pi｝，这是非确定的，每个分支耗时O(n)2. 验证p1*p2*…pi？=p-1，耗时不超过O(n^2)3. 若各因子乘积等于p-1，则用当前算法递归验证每个因子都是素数4. 随机选择p最小剩余系内的一个数x，计算x^((p-1)/q) （q遍历上述列表经过步骤3验证过的素因子）是否都不同余于1模p，若是则必有x^(p-1)同余于1模p，则由指数整除p的欧拉数及费马小定理，知p为素数，考虑到有少量的合数也满足费马小定理，故需多次选择x重复验证，选择个数最多为log(p)分析：本算法涉及的数论定理——设p是奇素数，p-1的所有素因子是q1,q2,…qs，那么g为原根的充要条件是，g^((p-1)/qj)不同余1模p，j=1,2…,s结论：第3步可以看成递归调用树，每个顶点为待检测整数，其每个子结点为一个因子，则最多n层，每层至多耗时O(n^4)，所以每个路径即检测p是否素数的非确定任一分支中，总耗时O(n^5)。 2002年，印度科学家发现素检测确定性多项式时间算法，于是从NP前进到了P春秋十二月2023-09-09 08:07发表评论 ...继续阅读 (90)