New answers tagged

3

While other answers approach the problem from the simpler question, "How do computer handle large number computation" the specific question is how computers handle large modulus numbers, and the answer is that there are algorithms and techniques specifically for handling large modulus calculations. Wikipedia provides a short list of terms and algorithms one ...


1

Since this is still open and the issue keeps coming up: TLDR: There are lots of things in OpenSSL that implement standards including AES, but the key derivation part of enc is partly nonstandard First, OpenSSL has several commandline operations it calls commands (although they usually aren't separate programs, as typical commands are on Unix), and a whole ...


1

If I understood well, you have two issues: About the $2\beta$ values of $x$ "generating" $\beta^2$ values About your the bugs in your code. So, answering (1): Notice that in the summation (and in your first for loop) for each $x_{i,0}$ you have $\beta$ different values of $x_{1,j}$, which means $\beta^2$ combinations of those $2\beta$ values. You are ...


3

As others have noted, you typically use some sort of arbitrary precision integer library. I feel obliged to point out, however, that extending multiplication to large integers is decidedly non-trivial compared to addition. With addition, you have a single bit of carry from one word to the next, and on a typical processor you even have an instruction ...


0

One important aspect to keep in mind, which I do not see in the other answers, is that in binary modulus 8192 is very easy, as 8192 is simply 2^13. If you take modulus in "normal" base 10, you'd call %100 simple. 1237659%100=59. You simply cut off everything before the last 2 digits. In binary, the same is true for %8192, or, written in binary, ...


49

It (or rather, the software running on it) will use arbitrary-precision ("bignum") arithmetic. The way this works is basically the same way in which you (probably) learned to do arithmetic on paper at school. The arithmetic taught to us humans at school is base-10 arithmetic — that is, we represent numbers as strings made up of ten different digits, ...


7

Of course the processor cannot process such large numbers directly; this is done though a library such as GMP. See Wikipedia for a list of such libraries, and a good textbook such as that of Gerhard and von zur Gathen for the underlying ideas. The freely available Handbook of Applied Cryptography also talks about this, especially in Chapter 14.


1

Find other software that does the test, then compare over the first 10^10 or more integers, then over random large numbers (both inside 64-bit range and significantly larger assuming your software does that). Try various bases. Use the Feitsma-Galway database of all 64-bit base 2 strong pseudoprimes and make sure you produce a similar results for all those ...


5

This is a good question, but I would consider hardcoding a known good group. There does not seem to be an advantage to letting the server decide if you can afford to use high enough parameter values. The SRP paper lists the following checks: "n is a large safe prime" (this is your first three points) "g is a primitive root of GF(n)" (your next point) "A ...


6

Well, the obvious thing to do is give it a long list of integers of known primality, and see whether the algorithm reports it correctly (with it occasionally reporting a composite as "relatively-prime" not being counted as an error, as long as it reports that value as composite at least 75% of the time). However, that simple-minded test might miss ...


1

So, I does anybody know how to design a module for remainder operation in >verilog that computes the remainder in a single clock cycle? Any links to >literature discussing the algorithm would suffice. A nieve implementation would be something like. parameter bitwidth; input [bitwidth-1:0] a; input [bitwidth-1:0] b; output reg [bitwidth-1:0] result; reg ...


4

You can (and should) do the reduction in constant time using masking. That is, instead of using the following (non-bitsliced) pseudo-C code to do the reduction: if ((result >> 8) & 1) { /* bit 8 is set: clear it and flip bits 0, 1, 3 and 4 */ result ^= 0x11b; } you can simply do: result ^= 0x11b * ((result >> 8) & 1); ...


3

A recent paper presented at FSE'2016 [1] addresses this exact question. In fact, it even provides a bitsliced implementation for the S-Box you are interested in Section 4. In summary: you first encode the existence of a bitsliced implementation as a SAT problem, use an off-th-shelf SAT-solver to solve it and finally retrieve the bitsliced encoding from the ...


1

Try to generate the Algebraic Normal Form (ANF) from the sbox step by step (i.e., with 2 bits and so on) or use something like http://cis.sjtu.edu.cn/index.php/A_Simple_Python_Script_for_Translating_Sbox_to_ANF_Boolean_Functions



Top 50 recent answers are included