标签: deterministic

这是我在这个网站上的第一个问题,我对RSA只有基本的数学理解,所以请耐心等待!:)

我正在为大学的最后一年项目编写一个Java Web应用程序.这是一个基于网络的实施"Pret-a-voter",一个安全的投票系统,适用于那些听过它的人.

基本上我的问题是我希望能够给某人履行审计员的角色:

• 一个源字节阵列(明文进行加密)
• RSA公钥文件
• 一个" 目标 "字节数组,这是我自己计算明文和公钥的密码数据的结果

然后,我希望审计员能够使用前两项执行加密,并确信第三项是结果.因此,我需要加密是确定性的,即每次重复使用相同的明文和公钥加密时生成相同的密码数据.

(注意 - 我在这个项目中的数据很小块的工作 - 有在所有涉及没有对称加密...我知道这是一个"有趣"的使用RSA的!)

无论如何我发现在Java中,使用

cipher = Cipher.getInstance("RSA");

使用默认的随机填充方案,在11个字节的成本(因此与2048位密钥对,这是可能的加密2048/8-11 = 245字节).对同一明文的重复加密会产生不同的密文,这显然不是我想要的ECB模式.

我的问题是 - 我应该使用以下内容吗？

cipher = Cipher.getInstance("RSA/ECB/NoPadding");

我已经在很多地方看到RSA没有填充而不安全.这仅仅是因为攻击者可以建立明文/密文字典吗？这是确定性的加密我需要为了让审计人员来验证我的加密的副作用,并在我的方案审核员信任,所以这将是确定.

我的问题的第二部分与java有关.如果我确实如上所述使用RSA/ECB/NoPadding,我相信我能够提供(例如)长度为128(对于1024位RSA密钥对)的源字节数组并加密以获得另一个长度的字节数组128.如果我再尝试加密是再次,与1024不同长度的公钥,我得到

javax.crypto.BadPaddingException:消息大于模数

有谁知道为什么？

编辑 - 使用NoPadding进行加密并不总能产生这种异常 - 这是一种性情.但是,即使加密没有生成此异常,解密也会生成:

javax.crypto.BadPaddingException:数据必须以零开头

非常感谢您阅读本文!任何帮助将不胜感激.

编辑 - 对不起,我原来的问题不是很明确我想做什么,所以这是一个[尝试]解释:

• 明文是选举中投票人的投票.
• 一个选民的目的是在不牺牲选民保密的情况下进行端到端的可核实(等).投票后,选民可获得一张收据,他们可以用来验证他们的投票是否已被正确记录,并且稍后会向他们表明他们的投票没有被篡改.选民将收据上的信息与网上发布的相同副本进行比较.
• 但是,任何选民都不应该证明他/她投票的方式(因为这可能导致强制),因此信息不是明文,而是加密的投票副本.
• 事实上,明文被加密了四次,有四个不同的非对称密钥 - 由两个不同的柜员持有,每个柜员拿着两把钥匙.因此,投票(明文)被提供给一个柜员,他使用公钥#1加密它,然后用他的第二个公钥加密THAT密文,给那个用他的两个密钥加密它的第二个柜员提供密文.办法.生成的密文(四个连续加密的结果)是发布到Web(公开)的内容.出纳员是值得信赖的.
• 每个加密的投票都可以看作是一个"洋葱",其中心是投票,并且有几层加密.为了得到表决,每一层又必须被去除,这意味着相应的私钥(由柜员保持)必须以相反的顺序施加.这是安全的关键 - 所有出纳员必须合作才能解密投票.
• 网络公告板可以显示为一个包含5列的表格 - 第一列(左侧)包含完全加密的投票(也显示在每个选民的收据上),并且是投票阶段唯一可见的列.第二列包含相同的投票集,但删除了外层 - 柜员2通过在统计阶段使用其私钥解密投票来填充此列和第3列.在计数阶段结束时,第5列包含完全解密的投票,然后可以计算.
• 每个选民都会得到一张收据,将他们与第1栏中的加密投票联系起来.这并未显示他们如何投票,但允许他们核实他们的投票未被篡改,因为在整个选举过程中他们可以验证他们的加密投票第1栏仍然存在,未触动过.当然,这只是"端到端验证"的一半,因为选民无法验证解密是否已正确完成,即第2列中有一个条目是他们的投票减去外层加密.每个选民只负责验证到第1栏的点.
• 此后,审核员有责任检查第1列中的条目是否解密到第2列,依此类推.他们这样做的方式是依靠确定性加密和用于加密的公钥是公开的.
• 由于公钥是公开的,你不希望人们只是简单地从第5列到第1列绘制线条,加入某人的投票,因为它变得反复加密 - 这样,将你绑定到加密投票的收据实际上将你绑定到未加密的,可读的投票 - >强制!因此,只有第1,3和5列是公共的(这就是每个出纳员执行两次加密的原因),对于第3列中的每个条目,{2,4}中只有一个相应的条目被透露给审计员.这可以防止任何人(甚至是审计员)将加密的投票链接到未加密的投票.
• 因此,审计人员需要在第3列中输入一个条目,在第2列和公钥中给出相应的条目,并执行相同的加密以验证它们确实在第2列中获得了条目.
• 总而言之,这提供了端到端的可验证性.

抱歉,这是如此冗长 - 我希望它描述了我对确定性加密的需求.我错过了很多基本细节(我已经大量修改了这个方案),但希望核心原则都存在.非常感谢你阅读 …

我想制作一些套装,每次运行程序都是一样的:

这是一种方法:

(def colours ["red" "blue" "green" "yellow" "cyan" "magenta" "black" "white"])

(defn colour-shuffle [n] 
  (let [cs (nth (clojure.math.combinatorics/permutations colours) n)]
    [(first cs) (drop 1 cs)]))

; use (rand-int 40320) to make up numbers, then hard code:
(def colour-shuffle-39038 (colour-shuffle 39038))
(def colour-shuffle-28193 (colour-shuffle 28193))
(def colour-shuffle-5667  (colour-shuffle 5667))
(def colour-shuffle-8194  (colour-shuffle 8194))
(def colour-shuffle-13895 (colour-shuffle 13895))
(def colour-shuffle-2345  (colour-shuffle 2345))

colour-shuffle-39038 ; ["white" ("magenta" "blue" "green" "cyan" "yellow" "red" "black")]

但是评估需要一段时间,而且看起来很浪费而且相当不优雅.

有没有一种方法可以直接生成shuffle 39038,而不会生成和消耗所有序列？

(我已经意识到我可以对它们进行硬编码,或者用宏来重新编译时间.这也似乎有点垃圾.)

我正在开发一款适用于iOS的Box2D物理多人游戏.多人游戏正常使用锁步法.游戏及时更新物理世界.具有相同CPU的iOS设备之间没有异步.

但是,当使用带有Apple A6芯片的新iOS设备进行测试时,发生了异步.查看我的日志文件给我的印象是,desync发生得非常快,可能是因为我找不到哪些浮点运算.

我可以保证只有Box2D是游戏设计中需要同步的唯一模块,并且所有mutliplayer命令和输入都不会根据我的日志不同步.

我试过改变所有超越函数:sinf,cosf,pow,sqrtf,atan2f到双版本,但没有任何运气.

有没有办法迫使Apple A6将浮点数与某些编译器选项一样处理Apple A5？

我真的很感激任何答案.

Delphi中的浮点运算是否具有确定性？

我将使用与Win64编译器,OS X编译器,iOS编译器或Android编译器一样的Delphi Win32编译器编译的相同可执行文件中的相同浮点数学运算获得相同的结果吗？

这是一个至关重要的问题,因为我正在我的游戏引擎中实现多人游戏支持,我担心客户端的预测结果可能经常与服务器的确定(和权威)决定不同.

其结果是当权威游戏状态数据否决客户端侧的预测状态时,在客户端出现"滞后"或"急躁".

由于我实际上没有能力在不同的编译器上编译的不同平台上测试数十种不同的设备,而这些设备类似于"受控条件",我认为最好将这个问题提交给Delphi开发人员,看看是否有人对编译器的低级浮点确定性有内在的理解.

因此,根据我对确定性谓词的理解:

确定性谓词= 1解

非确定性谓词=多个解决方案

是否有任何类型的规则可以检测谓词是一个还是另一个？喜欢看搜索树等

首先,我已经阅读了有关Prolog削减使用的所有其他帖子,并且肯定会看到与使用它们相关的问题.但是,对我来说仍然有些不清楚,我想一劳永逸地解决这个问题.

在下面的简单示例中,我们递归遍历列表并检查每个第2个元素是否等于1.执行此操作时,递归过程可能会在以下任一基本情况中结束:空列表或具有单个元素的列表仍然存在.

base([]).
base([_]).
base([_,H|T]) :- H =:= 1, base(T).

执行时:

?- time(base([1])).
   % 0 inferences, 0.000 CPU in 0.000 seconds (74% CPU, 0 Lips)
   true ;
   % 2 inferences, 0.000 CPU in 0.000 seconds (83% CPU, 99502 Lips)
   false.

?- time(base([3,1,3])).
   % 2 inferences, 0.000 CPU in 0.000 seconds (79% CPU, 304044 Lips)
   true ;
   % 2 inferences, 0.000 CPU in 0.000 seconds (84% CPU, 122632 Lips)
   false.

在这种情况下,我总是在第二个基本情况下使用显式切割运算符(即代表列表中剩下一个元素的那个),如下所示,以取消冗余选择点.

base([]).
base([_]) :- !.
base([_,H|T]) :- H =:= 1, base(T). …

我正在寻找Java用于序列化对象的格式.默认序列化以二进制格式序列化对象.特别是,我很想知道程序的两次运行是否可以不同地序列化同一个对象.

对象应该满足什么条件,以便对象在Java的默认序列化/反序列化往返中保持其行为？

在工作中,我们正在讨论新平台的设计,其中一个上层管理类型表示它需要运行我们当前的代码库(C on Linux),但需要实时,因为它需要在不到一秒的时间内响应各种输入.我指出:

1. 这一点并不意味着它需要"实时",因为它需要更快的时钟和更多的中断处理流程
2. 要考虑的关键点之一是正在使用的操作系统.他们想坚持使用嵌入式Linux,我指出我们需要一个RTOS.由于内核/用户空间内存分裂,使用Linux将阻止"实时",因此I/O通过引入延迟的文件和套接字完成
3. 我们真正需要确定的是它是否需要确定性(例如,需要在90%的时间内以<200ms响应输入).

真的在我的脑海中,如果第3点是真的,那么它需要是一个实时系统,然后第2点是最大的考虑因素.

我有信心回答,但后来我想到了......别人怎么想？我在这里是正确的轨道还是我错过了什么？

在"实时"系统和"确定性"系统之间我是否有任何不同之处？除了RTC和RTOS之外,我还缺少执行真正实时系统所需的任何主要内容吗？

期待一些伟大的回应!

编辑:

到目前为止得到了一些好的回答,看起来对我的系统和要求有一点好奇,所以我会为感兴趣的人添加一些注意事项:

1. 我的公司销售数十万的单位,所以我不想在价格上超过杀人
2. 通常我们销售主处理器板和独立显示器.还有一个其他CAN设备的连接网络.
3. 电路板(当前)运行设备,还充当网络服务器,为最终用户向显示器发送基本XML文档

这里的要求是管理层希望"快速"(<1s)更新显示,但IMO 的真正限制来自可通过CAN连接的设备.这些设备通常是电机控制设备,其要求包括"必须在小于200ms内响应".

?: Q × ? ? Q用英语怎么说？描述什么×和?意思也会有所帮助.

过去我曾处理过时间紧迫的软件开发。这些应用程序的开发基本上是这样进行的：“让我们编写代码，测试延迟和抖动，并对两者进行优化，直到它们处于可接受的范围内。” 我觉得这非常令人沮丧；这不是我所说的正确的工程，我想做得更好。

所以我研究了这个问题：为什么我们会有抖动？答案当然是：

• 缓存：从主内存获取一段代码或数据比从 L1 缓存获取相同数据要多花费 2 个数量级的时间。所以物理执行时间取决于缓存中的内容。这又取决于几个因素：
  • 应用程序的代码和数据布局：我们都知道可怕的行主与列主矩阵遍历示例
  • CPU 的缓存策略，包括缓存行的推测性预取
  • 同一核心上的其他进程正在做事情
• 分支预测：CPU 尝试猜测条件跳转的哪个分支将被执行。即使相同的条件跳转执行两次，预测也可能不同，因此一次可能会形成“管道泡沫”，而另一次则不会。
• 中断：异步行为显然会导致抖动
• 频率缩放：幸好在实时系统中被禁用

有很多事情会干扰一段代码的行为。尽管如此：如果我有两条指令，位于同一缓存行，不依赖于任何数据，也不包含（条件）跳转。然后，应该消除缓存和分支预测带来的抖动，并且只有中断才能发挥作用。正确的？好吧，我编写了一个小程序，获取时间戳计数器 (tsc) 两次，并将差异写入标准输出。我在一个打了 rt 补丁的 Linux 内核上执行了它，并且禁用了频率缩放。

该代码具有基于 glibc 的初始化和清理，并调用 printf，我认为它有时在缓存中，有时不在缓存中。但是在调用“rdtsc”（将 tsc 写入 edx:eax）之间，二进制文件的每次执行都应该是确定性的。为了确定起见，我反汇编了 elf 文件，这里是两个 rdtsc 调用的部分：

00000000000006b0 <main>:
 6b0:   0f 31                   rdtsc  
 6b2:   48 c1 e2 20             shl    $0x20,%rdx
 6b6:   48 09 d0                or     %rdx,%rax
 6b9:   48 89 c6                mov    %rax,%rsi
 6bc:   0f 31                   rdtsc  
 6be:   48 c1 e2 20             shl    $0x20,%rdx
 6c2:   48 09 d0                or     %rdx,%rax
 6c5:   48 29 c6 …