二元推导与自相关随机性检测算法的相关性分析

随机性检测在密码学中发挥着重要的作用,目前,已有多种不同的随机性检测算法.但是,实际应用中选择所有的检测算法进行检测不现实,选择哪些算法能够使检测充分且无冗余,这需要研究检测算法之间可能存在的关系.对两种重要的随机性检测算法二元推导和自相关进行了研究.从二者的基本原理出发,对其检测的推导过程进行了分析,结合杨辉三角的性质证明了在参数k选择为2t 时,二元推导与自相关是等价的.若同时进行参数为2t的二元推导检测和自相关检测则存在冗余.同时对这个结论进行了实验验证.另外,研究还发现,在参数k选择为2t一1时,二元推导检测中推导序列的每一个比特包含初始序列的所有相关比特信息.所研究工作为实际应用中随机性检测项目和检测参数的选择提供了理论的指导.     

随机序列的扑克检测优化研究

现代计算机系统的安全性依赖于二元随机序列,随机性检测利用概率统计方法对二元序列的随机性进行分析测试。我国国家密码管理局发布了随机性检测规范,扑克检测为其中一个检测项。本文通过充分分析扑克检测效率不高的原因有针对性地提出一种新的快速实现算法,优化算法充分利用CPU字长一次处理多个比特,将m为4和8的情况整合在一起,减少不必要的处理流程。同时精简并优化统计量的计算和判断过程,避免余不完全伽马函数的计算。分析和实验的结果表明该优化算法可以使得扑克检测的速度提升9.5倍左右。     

基于卷积码的数字图像认证

提出一种基于卷积码的彩色图像认证算法。对图像RGB颜色通道的高位比特进行卷积编码,把监督比特隐藏在低比特位中,实现对彩色图像的篡改检测和篡改定位,并保持编码后图像的不可感知性。编码后的图像可以在没有原始图像的情况下,在像素级别上对篡改进行检测和定位,并有一定的图像自恢复能力。实验结果表明,基于卷积码的彩色图像认证算法实现简单、性能可靠,编码后的图像具有很好的篡改检测、定位性能。     

H.265/HEVC中基于R-λ模型码率控制的优化算法

在H.265/HEVC基于R-λ模型码率控制算法中,为了提高最大编码单元（LCU）的比特分配的效果以及参数（α、β）更新的精度,提出一种码率控制优化算法。该算法主要是利用当前最大编码单元原始比特进行比特分配,以及利用编码失真度对参数（α、β）更新。实验结果表明,在恒定比特率情况下,相对于HM13.0码率控制算法三分量峰值信噪比（PSNR）增益至少提高0.76 dB,编码传输比特每帧消耗比特至少降低0.46%,编码时间至少减少0.54%。     

一种快速相关攻击算法

提出一种针对序列密码的改进的快速相关攻击算法。将序列密码的攻击问题转化为线性分组码的译码问题,采用最大似然译码方法进行译码。利用Walsh变换进一步优化算法的计算复杂度。对算法中的穷搜索比特数和校验方程重量2个关键参数的选取进行探讨,从理论上推导出校验方程重量与算法攻击成功概率之间的解析关系,为选取参数提供了依据。仿真结果表明,该算法性能优于之前的快速相关攻击算法。     

基于SCM的自适应抽头伪随机相位生成算法

为使基本调制波形的相位随机性最大化以提高变换域通信系统的射频隐身性能,提出基于标准混沌映射(Standard Chaotic Map,SCM)的自适应抽头伪随机相位生成算法。首先由标准混沌映射产生混沌现象,通过中值法对混沌数值进行二元量化生成伪随机序列,结合映射抽头的 “跳变图案”,在线性移位寄存器中自适应地选取抽头进行伪随机相位生成,由此推导出检测概率与截获概率的解析式,将低概率检测与低概率截获的目标转化为控制参数的优化,从而使相位随机性最大化。理论分析与仿真结果表明该算法生成FMW的检测概率为现有m序列FMW检测概率的 ,降低了检测概率,因而也降低了截获概率,增加截获难度。     

基于矩阵概率检验的Zigbee协议随机性检测方法

随机性检测是研究密码算法基础理论的重要内容。为了有效测试与鉴别物联网系统中Zigbee协议采用密码算法的安全性,本文结合Zigbee网络的特点,在二元矩阵秩检验的基础上对测试方式进行了合理的组织与划分,提出基于矩阵概率检验的Zigbee随机性检测方法,解决了二元矩阵秩检验单纯从线性相关性判断随机序列的片面性,并能有效地判断Zigbee协议是否实施了加密机制以及加密强度。仿真结果表明,该算法具有误差较小、可靠性高等特点,检测结果更具说服力,为物联网系统的信息安全测评提供理论和实践指导。     

基于区域随机性度量的LSB匹配隐写分析

依据图像信源区域平稳性质,分析LSB匹配隐写对图像区域统计特性的影响,提出一种基于区域随机性特征的隐写分析方法.运用分块处理划分图像区域,对各区域像素进行Hilbert扫描并提取像素最低有效位比特序列,进而将比特序列作异或运算所得到的参量定义为区域随机性度量指标,最后统计并分析区域随机性指标直方图,提取直方图信息熵、特殊取值及原点矩3类特征,结合Fisher线性分类器对载体、载密图像进行判别.实验结果表明,该方法在不同图像库和不同嵌入率条件下对LSB匹配隐写均表现出良好的检测性能,与现有典型检测算法相比其检测性能具有明显提高.     

序列检测和近似熵检测的快速实现研究

随机序列广泛应用于信息安全领域,随机序列的质量依靠随机性检测规范判断。美国国家标准与技术研究院提出的随机性检测规范中包含序列检测和近似熵检测,这两种检测算法的运算速度位列检测包末端。对两种检测算法的运算流程进行研究,通过优化字节处理方式、字节运算与相对频数统计相结合、频数统计值复用等方法分别优化两种算法,并将两种检测算法进行合并,减少冗余的数据加载和处理流程,完成两种算法的快速实现。实验结果表明,不同参数下序列检测和近似熵检测速度最高分别提升30.02倍、27.58倍,两种检测合并后整体速度最高提升45.23倍。     

基于数模混合的真随机数发生器

提出了一种数模混合的真随机数发生器设计方案,利用RC电路充放电时间的不稳定性作为随机噪声源,并采用8个噪声源模块并行工作.8个噪声源模块产生的16比特随机数经由模加、异或、移位和反馈组成的算法处理后输出8比特分布均匀、相互独立的随机数,同时为了方便外部应用,设计了串并行输出单元.将整个真随机数发生器在Spectre模拟器下进行了仿真与测试,结果表明,随机数生成速率为3.2MHz,且能够通过FIPS140-2的随机性检测.     

RESTRICTING THE WEAK-GENERATIVE CAPACITY OF SYNCHRONOUS TREE-ADJOINING GRAMMARS

The formalism of synchronous tree-adjoining grammars, a variant of standard tree-adjoining grammars (TAG), was intended to allow the use of TAGs for language transduction in addition to language specification. In previous work, the definition of the transduction relation defined by a synchronous TAG was given by appeal to an iterative rewriting process. The rewriting definition of derivation is problematic in that it greatly extends the expressivity of the formalism and makes the design of parsing algorithms difficult if not impossible. We introduce a simple, natural definition of synchronous tree-adjoining derivation, based on isomorphisms between standard tree-adjoining derivations, that avoids the expressivity and implementability problems of the original rewriting definition. The decrease in expressivity, which would otherwise make the method unusable, is offset by the incorporation of an alternative definition of standard tree-adjoining derivation, previously proposed for completely separate reasons, thereby making it practical to entertain using the natural definition of synchronous derivation. Nonetheless, some remaining problematic cases call for yel more flexibility in the definition; the isomorphism requirement may have to be relaxed. It remains for future research to rune the exact requirements on the allowable mappings.     

Conjugate schema and basis representation of crossover and mutation operators

In genetic search algorithms and optimization routines, the representation of the mutation and crossover operators are typically defaulted to the canonical basis. We show that this can be influential in the usefulness of the search algorithm. We then pose the question of how to find a basis for which the search algorithm is most useful. The conjugate schema is introduced as a general mathematical construct and is shown to separate a function into smaller dimensional functions whose sum is the original function. It is shown that conjugate schema, when used on a test suite of functions, improves the performance of the search algorithm on 10 out of 12 of these functions. Finally, a rigorous but abbreviated mathematical derivation is given in the appendices.     

基于类别可分离性的遥感图象特征提取方法

本文从类别可分离性出发推导出一种用于遥感图象特征提取的线性变换方法.该方法并 不着眼于变换子空间的整体信息保持,而在于使当前待分类别具有最好的分离度.文中给出 了变换核的理论推导及计算方法.试验结果表明该方法具有良好处理效果.     

On deriving test suites for nondeterministic finite state machines with time-outs

In the paper, the non-separability relation for finite state machines with time-outs is studied. A specific feature of such machines is integer-valued delays, or time-outs, which determine how long the finite state machine will stay in one or another state if there are no input actions. If the time-out is over and no input symbol has been applied, then the TFSM state is changed according to the transition under time delay. In the paper, an algorithm for constructing a separating sequence for such finite state machines is presented. Here, the separating sequence is a timed input sequence for which sets of input sequences of the TFSM do not intersect; hence, it is sufficient to apply the separating sequence once in order to distinguish the TFSMs by their output reactions. This algorithm underlies the algorithm for construction of test suites with respect to non-separability relation in the case where the fault domain is specified by means of a mutation machine. Test suite derivation with respect to non-separability relation by way of ??TFSM to FSM?? transformation is discussed.     

荷兰国旗问题的形式化推导及其多态性实现

讨论了程序功能规约变换和算法程序的形式化技术，通过功能规约变换，可以较自然地获得问题求解的递推关系，对荷兰国旗问题的求解过程显示了形式化推导在获得高效和正确的算法程序中的作用。最后，给出了问题求解的多态性实现。     

产品目录中型别派生的算法研究

在基于MRPII(制造资源计划)思想的生产管理系统的研发中,基础数据的有效维护是系统成功实施的关键,针对国内航空企业产品系列化中存在的产品型别派生问题,提供了产品型别组合关系的派生算法,并在系统中实现,解决了产品目录输入维护的关键问题,缩短了生产管理系统投入运行的准备时间;且此算法对于类似系统具有普遍参考价值。     

一种测试语言包含的算法

在积自动机基础上,利用互模拟关系引出商自动机,用以解决积自动机的状态组合爆炸问题。进而提出一个自然的测试语言包含的算法,这种算法的空间复杂度与规范自动机的状态目呈指数关系即O（2^k),其中K是规范自动机的状态数目。     

Automated reasoning in differential geometry and mechanics using the characteristic set method

This is the first paper of a series of three papers under the same title. It presents an improved version of Ritt-Wu's decomposition algorithm which is the basis of our methods of mechanical theorem proving and mechanical formula derivation in differential geometry and elementary mechanics. We improve the original algorithm in two aspects. First, by using the weak ascending chain and W-perm, the sizes of the differential polynomials occurring in the decomposition can be reduced. Second, by using a special reduction procedure, the number of branches in the decomposition can be controlled effectively. The improved version significantly enhances the efficiency of the original algorithm.The work reported here was supported in part by NSF Grants CCR-8702108 and CCR-9117870.     

基于小波变换和方向微分的运动模糊方向鉴别研究

针对最小方向微分算法(MinimumDirectionalDerivation,MDD)在运动模糊方向鉴别中计算量大的问题,提出利用小波变换和方向微分相结合的算法鉴别运动模糊方向。首先引入小波变换获得运动模糊图像的低频部分,缩小了计算范围,减小了计算量;然后在利用基于方向微分的加权平均法鉴别模糊方向时,先取步长为10°粗略得到模糊方向,在此模糊方向±10°范围内以0.5°为步长精确鉴别出模糊方向。该方法既能减小计算量,又能提高鉴别精度。仿真结果表明本文算法鉴别运动模糊方向误差小,实时性好,应用范围广。     

Testing in context: framework and test derivation

The paper addresses the problem of testing a component embedded within a given modular system. A context of the component represents the rest of the system and serves as its operational or testing environment. A framework for testing in context is presented based on the model of a system of communicating finite state machines. In particular, the problems of test executability and fault propagation in the presence of the context are identified and discussed. The proposed solution to these problems consists in computing so-called approximation of the specification in context, i.e. the FSM model of the component's properties that can be controlled and observed through the context. The approximation assures executability of tests and fault propagation through the context and serves as a base for test derivation. A conformance relation used for test derivation is shown to be the reduction relation between an implementation and the approximation of the given specification. This relation requires that the implementation produces a (sub)set of output sequences that can be produced by its specification in response to every input sequence. An approach to test generation for the reduction relation and deterministic implementations is also presented.