4

The formulas are equivalent. From §3.2: $e \cdot d \equiv 1 \pmod{\lambda(n)}$, i.e. $e \cdot d - 1 \equiv 0 \pmod{\lambda(n)}$, i.e. $\lambda(n)$ divides $e \cdot d - 1$. From §3.1: $\lambda(n) = \mathrm{lcm}(p-1, q-1)$, so $p-1$ divides $\lambda(n)$. Therefore $p-1$ divides $e \cdot d - 1$, i.e. $e \cdot d - 1 \equiv 0 \pmod{p-1}$, i.e. $e \cdot d \equiv 1 ...


4

Can modular exponentiation with a public index be considered a secure permutation? I'll assume the permutation thought is $f_{(n,e)}:\ x\mapsto x^e\bmod n$ with odd $n>2$, odd $e>1$, and $x$ in the set $\{0,1,\ldots n-2,n-1\}$ less some subset of $\{0,1,n-1\}$. $f_{(n,e)}$ is a permutation when $n$ is square-free, and $e$ is coprime with $\varphi(n)$. ...


4

Is there any advantage to use $\bmod q$ over naïve method (without using modulo)? If yes, is it security or computational complexity or any other? Yes; doing things $\bmod q$ does have the practical advantage that the shares are bounded length; computing the shares in $\mathbb{Z}$ can potentially have us send rather long values (as the values there don't ...


3

The question's code computes the 64-bit get<2>(I)=$h:=f\,g\bmod n$ from inputs: 64-bit modulus_value=$n$ with $n\in[2,\,2^{63}]$ 64-bit get<0>(I)=$f$ with $f\in[0,\,2^{64}-1]$ 64-bit get<1>(I)=$g$ with $g\in[0,\,2^{64}-1]$ and $f\,g<2^{64}\,n$, a condition that's met if $f,g\in[0,\,n-1]$ (which I guess is always the case in the ...


3

What you are using is the so-called Text-Book RSA. For encryption, we always want the correctness requirement and for public-key systems, this is; $$D(prv,(E(pk,m)) = m$$ where $E$ is the public key encryption with the public key ($pk$) and $D$ is the decryption with the private key ($prv$). In Text-Book RSA if we let the messages $m\geq n$ then as you ...


2

Is there an easy way to recover $p$ and $q$? Yes (in all cases except for $B, D$ are both multiples of $N$, or $k=0$, and assuming that $p, q$ are distinct primes) Let us assume that $B$ is not a multiple of $N=pq$; then: If $B$ is not a multiple of $p$, then $\gcd(A, N) = q$ (because $A=Bq^k$ is a multiple of $q$ but not $p$); simple division also ...


2

If $p-1$ has a factor of 348419, then you could reduce the number of possible values of $S$ to 348418 (or 1, which you said was not allowed). One way to do this would be to pick a random value $r$, and compute $k = r^{(p-1)/348419} \bmod p$; if $k$ is something other than 1, then that's your value; the eventual $S$ value will be $k^x \bmod p$ for some $1 \le ...


2

I think somehow since $pin \in [0,9999]$ we should be able to brute force the value but I am unable to come up with the math to do so. Unless the random number generator is broken, there is no way to recover pin; this would remain true even if we were able to compute discrete logs mod $P$ (which we can't). The issue is that the public key is generated as: $$...


2

Note that $$\frac{7(p-5)}8+3=\frac{7p-11}8\equiv \frac{7p-11}8-p-1\equiv -\frac{(p+3)}8\pmod{p-1}.$$ Similarly $$\frac{p-5}8+1=\frac{p+3}8$$ And so $v^3(v^7)^{\frac{p-5}8}\equiv v^{-\frac{(p+3)}8}\pmod p$. Likewise $u(u)^{\frac{p-5}8}\equiv u^{\frac{p+3}8}$ as required. The reason is to save a modular division which is quite a pricey operation.


2

Using that $\forall x\in\mathbb Z$, it holds $x\bmod p\,=\,p-1-((-x-1)\bmod p)$, and that in so-called two's-complement arithmetic $-x-1$ is the bitwise complement of $x$, the other answer's code simplifies to: uint32_t imod(uint32_t x, uint32_t p) { uint32_t s = -(x>>31); // 0 or -1, with the later iff x<0 x = x ^ s; ...


2

This answer answers Q1, as there may be merit other than just for calculating CRT RSA (e.g. the extended Euclidean algorithm). Let's build it step-by-step. First let's assume you've implemented the % operator for unsigned modular arithmetic in constant time, when you encounter a negative number x, we have the following: x === -(-x) Introducing the modulus p,...


2

is there a way to find n (n is 2048 bits)? Yes, if you assume deterministic padding (which is sometimes used for signatures, which appears to be the case you're considering) You're on the right track by considering $c^e - m$ (which will be a multiple of $n$); given that we have several, what we can do is take two, and compute: $$\gcd( c^e-n, c'^e-m' )$$ ...


2

We have $\varphi(t)|\varphi(pt)$ and $\varphi(t)|\varphi(qt)$ so that if $d_1$ and $d_2$ are the exponents for $s_p^*$ and $s_q^*$ then $d=d_1+k_1\varphi(t)$ and $d=d_2+k_2\varphi(t)$ for some integers $k_1$ and $k_2$. It follows that $d_1=d_2+(k_2-k_1)\varphi(t)$ and hence $$d_1\equiv d_2\pmod{\varphi(t)}.$$ It follows that $m^{d_1}\equiv m^{d_2}\pmod t$ by ...


2

It is easy to show that in RSA, when e = 3 there are 4 messages m for which the ciphertext is equal to the plaintext and gcd(m, n) = 1 Well, if $m^3 = m \pmod n$ (and assuming $n$ is a conventional RSA modulus, that is, it is $n = pq$, for $p, q$ distinct odd primes), this is equivalent to both of the below holding simultaneously: $$m^3 = m \pmod p$$ $$m^3 =...


2

What about:- $$ n_s = \mathcal{H}(n_b) \& (2^{32} - 1) $$ where $n_b \in N_b$, etc? $\mathcal{H}$ can be a hash function of your choosing. Since this is a crypto site, I suggest SHA-256. $\&$ means bitwise AND, but could be replaced with right or left shifts of the appropriate number of bits (128 in SHA-256's case). Too slow perhaps(?) ...


1

The question apparently aims to find something like: the bit representation of an integer $a$ when working modulo $m$. This is not well defined. We'll suppose that instead, it's wanted the bit representation of the integer $a\bmod m$. By definition, the integer $a\bmod m$ is the integer $r$ with $0\le r<m$ and $a-r$ a multiple of $m$. When $a\ge 0$, this $...


1

The problem of solving for $N$ the equation $G^N\equiv A\pmod P$ for given integers $P$, $G$, $A$ is generally stated for integer $N$ with $0<N\le Q$ for some $Q<P$. The function $N\mapsto G^N\bmod P$ is periodic. Hence if $N$ is a solution, the set of all solutions is obtained by adding a multiple of the period¹ of that function to that $N$. Thus it's ...


1

This will depend on the language that you implement in. Java and other C-like languages have a built-in data type to represent unsigned 32-bit integers (this is why RC6 chose to use this form of arithmetic, so that its implementation in these languages is relatively straightforward). In such cases +, -, and * all automatically work mod $2^{32}$. If you're ...


1

If I understand the requirements, what you are asking for is not a "function" according to the normal definition. It sounds like you want some $f$ that given a sequence of inputs ${x_i}$ will return either a deterministic value $y_i$ or an error symbol if it has already returned $y_i$. But suppose $x_k$ is the first input to return an error. What ...


1

Consider $f: x\mapsto f(x)=\underbrace{x+x\ldots x}_{a\text{ times}}+b\bmod 2^{32}$ in the the ring $(\mathbb Z_{2^{32}},+,\times)$, where $a$ and $b$ are constants. Per one meaning, $f$ is linear, that is of the form $x\mapsto a\times x+b$, for constants $a$ and $b$. Per another meaning, $f$ is not (in general) a linear boolean function. $f$ is also not ...


1

If you divide the whole equation throughly 2 you get $$31a\equiv 19\pmod {34}$$ which you can solve to get $a\equiv 5\pmod{34}$. This then gives two possibilities for $a\pmod {68}$: either 5 or 39. For these two possibilities you can then find the corresponding $b$ (it turns out to be 5 in both cases) and check which solution works.


1

To answer a specific question: Are benchmarks simply being run in a vacuum and not in production? Well, yes, pretty much. If you are running a serious performance test on a specific routine, you deliberately don't run anything else (because whatever else the computer is doing at the time will jitter the timing of the routine you'll looking at, making the ...


1

Can you give me some hints? It's not a proof of knowledge, as someone without knowledge of $x$ can complete this protocol successfully with an honest verifier. Hint: what happens if the ignorant prover sends $y = h^{-1}$?


1

The powers of $2$ modulo 11; \begin{array}{c|rrrrrrrrrrrrrrrr} x& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10\\ \hline 2 ^x \bmod 11& 2& 4& 8& 5& 10& 9& 7& 3& 6& 1 \end{array} We don't need the above 10 due to the Little Fermat Theorem; for a prime $p$ and $p\not| a$ then $$a^{p-1} \equiv 1 ...


1

so my goal is to make an encryption method that swap the characters to the proper places. If that's the goal, that's what you do. You were thinking about "how do I generate the $g$ (actually, the $l, d$ values) in the reverse order"; actually, there's no need. You just compute the successive $l, d$ values generated by the algorithm, storing them ...


1

The proposed system is close to the safe RSA-KEM, with some exceptions: The condition $\gcd(P-1,e)=1$ and $\gcd(Q-1,e)=1$ is missing. This must be checked when generating $P$ and $Q$. In the case of prime $e$ (as in the question) this simplifies to $P\bmod e\ne1$ and $Q\bmod e\ne1$. The random key is 512‑bit, when in RSA-KEM it is typically drawn in $[0,P\,...


1

It is quite simple to convert MTI/A0 into an elliptic curve method. An implementation is here.


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