# Tag Info

11

Thomas' first procedure produces 2 bits per roll with a probability of $\frac23$, i.e. it produces $\frac43 \doteq 1.333$ bits on the average. This can be improved as he describes, but it gets quite complicated soon. Producing a single bit per roll by taking the result mod two leads to $1$ bit per roll, which is not much worse. Combining the two simple ...

7

The obvious approach is to consider the following bit extraction algorithm: Roll the die, producing an integer $n$ uniform in $\mathbb{Z}_6$. If $n < 4$, return $n$ as two bits. Otherwise, go to 1. This will return two uniform bits. The algorithm will always terminate, since the probability of recursion is equal to $\frac{2}{6}$ which is ...

4

Firstly, $|\mathbb Z_n|=n$, whereas $|\mathbb Z_n^*|=\varphi(n)<n$. So, by the pigeon-hole principal there cannot be a mathematically invertible function $f:\mathbb Z_n\to\mathbb Z_n^*$. So, lets relax our idea of what 'invertible' means a bit. How about ensuring every element of $\mathbb Z_n^*$ has a preimage? Yep, we can do that. To use a couple of ...

4

Timing attacks against a function $f_k$ generally require two things: The attacker might observe the target perform $f_k(x)$ for a large number of sufficiently diversified known inputs $x$. For each $k$, there are inputs $x$ and $x'$ such that $f_k(x)$ and $f_k(x')$ are expected to execute at different speed. Now, let's assume $f_k$ is the private key ...

3

In cryptography, addition modulo $n$ (where $n$ is a positive integer, maybe $n=32$ as in the original question, or $n=2^{32}$ as in the revised question) is usually understood as the application from $\mathbb Z\times \mathbb Z$ to $\mathbb Z$, $(a,b)\mapsto c$ with $c$ such that $0\le c<n$ and $(a+b-c)$ is a multiple of $n$. That's also a common sense in ...

3

1 way to get 3 bits of entropy from a single die roll is as follows : Roll the fair die For 2,3,4,5 yield two bits {01,10,11,00} and go to 4, for 1 or 6 yield {1,0}. For the number on the die appearing right-way-up to the thrower (0-179 degrees) yield {0} for the number on the die appearing upside-down to the thrower (180-359 degrees) yield {1} and go to ...

2

Yes, as @DrLecter said in the comments, that equation holds from the bilinear property. Here is a step-by-step proof. Let $e : \mathbb G_1 \times \mathbb G_2 \to \mathbb G_T$ be a bilinear pairing. The bilinear property states that: \begin{align}e(g_1 ^ a, g_2 ^b) = e(g_1,g_2)^{ab}\end{align} Since you don't seem to distinguish between $\mathbb G_1$ and ...

2

In your setting this is assumed to be hard. It is exactly the task of producing a forgery for message $s$ of the weakly secure Boneh-Boyen signature scheme (Sec. 3.1) under public key $g^{e_1}$ (note that the scheme is presented in the asymmetric setting but can equally be instantiated in the symmetric setting under the $q$-SDH assumption). In other words, ...

2

The first byte is 0x00, because some standards allow RSA key sizes $8b+1, b \in \Bbb Z_+$. Such key would have 0x01 at the first bit, but it is possible for almost all other bits to be zero. Thus, 0x00 as the first byte allows interoperability with all possible RSA key sizes. NIST's recommendations and few other standards actually recommend only few ...

2

There is no known way to compute $(g^a)^k \mod p = g^{ak} \mod p$, given only $g^k \mod p$ and $g^a \mod p$ as per the Decisional Diffie–Hellman assumption. This is roughly equivalent to the discrete log problem. This is described in more detail in this paper.

2

To answer your question: it's expected, because you're using the wrong modulus. CodesInChaos pretty much gave you the correct answer; I'll try to explain in more detail about what's actually going on. We can define an elliptic curve based on any finite field $GF(p^k)$; in the case of P=256, we have ...

2

Efficient constant-time exponentiation algorithms exist. For example, one could calculate a sequence as follows: Given $a^{k}, a^{k+1}$ calculate either $a^{2k+2}, a^{2k+1}$ or $a^{2k}, a^{2k+1}$. Both calculations differ only in which value is squared and which is multiplied, making them easy to implement with a single conditional swap as the only ...

2

I think you have a lack of knowledge on pairings and finite fields. Your definition of the pairing $e(X,Y)=g^{XY} \bmod p$ is not correct. A pairing is defined as a map $e : \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T$ with the property \begin{align}\text{for all }g_1 \in \mathbb{G}_1 \text{ and } g_2 \in \mathbb{G}_2: e(g_1^a,g_2^b) = ...

Only top voted, non community-wiki answers of a minimum length are eligible