3

There are two reasons for not using $\varphi(n)$ during encryption. The first one is that it doesn't work - you can verify this by looking at the RSA correctness proof. It requires, that the modulus is $n$. The second one is - if you know $\varphi(n)$ you can efficiently compute $d$ given $e$, and therefore know the private key.


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 ...


3

One thing you can always do in situations like this is "defer the reductions to the end". By this, I mean do all of your calculations in $\mathbb{Z}[x]$, and then at the end "perform reductions until you no longer can", where the two kinds of reductions you do in $\mathbb{Z}/p\mathbb{Z}[x]$ are: Modular reductions (of coefficients): $a\...


3

How can I eliminate square roots before I go all the way down the "tree"? The obvious thing to do is eliminate intermediate values that are not quadratic residues. Here is one way to do it: Define the set s := [ c ], that is, s initially consists of a single element c. For i := 0 to 63 do Set the set t := [], that is, initialize it to be the ...


3

Well, lets see if we can go through it from the basics. $x \bmod y$ is the unique integer $x + \ell y$ that satisfies $0 \le x + \ell y < y$, for some integer $\ell$ (which might be positive, negative or zero) I will skip the parts that prove that, if $x, y$ are both integers and $y > 0$, then there exists such an $\ell$ and it is, in fact, unique. ...


3

Well, if we assume that: $e$ is prime (65537 is) Only one of the primes minus one has $e$ as a factor; for example, $p-1$ is divisible by $e$, but $q-1$ is not. For this discussion, we'll assume that $p$ is the prime with $p-1 \equiv 0 \bmod e$ (which might happen to be the size 1023 factor for you) $p-1$ is not divisible by $e^2$ That the ciphertext was ...


2

Moderator note: This answers a different question that I incorrectly merged: Consider a number $r$ obtained by: $\quad r=a⋅b\bmod n$ Can knowing the factorization of $r$ reveal some information (bits) of $a$ and $b$ ? The factoring of $r$ is not unique $\pmod n$.


2

Just sample a random $x$, and $[(g^x \bmod p) \bmod H]$ will equal your target value $h$ with probability $1/H$. After trying $O(H)$ candidates you will find a preimage. Fine print: Technically speaking, the probability isn't exactly $1/H$. Each $h \in \mathbb{Z}_H$ has either $\lfloor \frac{p-1}{H} \rfloor$ or $\lceil \frac{p-1}{H} \rceil$ preimages under ...


2

The RSA problem, which you describe, is not known to be equivalent to factoring and there is evidence both ways. In [BV] it is shown that this barrier might be inherent: using a black-box separation technique called meta-reductions, they show that certain restricted class of reductions are not possible. On the other hand, it was shown later in [AM] that in ...


2

Let $g(x) = (x^8+x^4+x^3+x+1)$ and $p(x) = (x^7+x+1)$ The GCD is correct and it is $1$ as the last non zero remainders. \begin{align} (x^8+x^4+x^3+x+1) &= (x^7+x+1)(x) + \color{blue}{(x^4+x^3+x^2+1)}\\ (x^7+x+1) &= (x^3+x^2+1)\color{blue}{(x^4+x^3+x^2+1)} + \color{red}{(x)}\\ (x^4+x^3+x^2+1) &= (x^3+x^2+x)\color{red}{(x)} + 1\\ \end{align} Now ...


2

In a chosen ciphertext attack, it is hypothesized that the adversary can obtain the decryption of cryptograms chosen by the adversary other than the targeted one(s), and in addition obtain the encryption of any message chosen by the adversary (which is free for asymmetric encryption). The most general CCA experiment goes: Key generation: the challenger ...


2

TL;DR: the second method works only for a vanishing proportion of primes $p$. The question uses the same relation between $a_1$ and $a_2$ as in the Pohlig-Hellman symmetric cipher. In this: $p$ is a public prime parameter, the encryption key is a random integer $a_1$ coprime with $p-1$, the decryption key is an integer $a_2$ such that $a_1\,a_2=k\,(p-1)+1$ ...


2

The Galois Field $\operatorname{GF}(2^4)$ (also represented $\mathbb{F_{2^4}}$) contains $16 = 2 ^4$ elements. The formal definition is; $\mathbb{F_{2^4}}$ is the quotient ring $\mathbb{F_{2}}[X]/(x^4 = x + 1)$ of the polynomial ring $\mathbb{F_{2}}[X]$ by the ideal generated by $(x^4 = x + 1)$ is a field of order $2^4$. We can list the elements of $\...


2

This algorithm is computing $$I'=I\cdot Y^N\bmod X$$. Using a standard square and multiply algorithm you need at most $\lceil 2\log_2(N)\rceil+1$ modular multiplications to compute $I'$. This is about 33 multiplications for the given example of $N=10,000$ which probably counts as this algorithm being "predictable".


2

The following two videos are recommended. They show how to apply Chinese Remainder Theorem (CRT) and implement Cocks' public encryption system. I recommend the following two videos: "Demo of Chinese Remainder Theorem" by "D G" (24min) which explains how $(x\bmod p,x\bmod q)$ can be used to find $(x\bmod n)$ "Cocks' Non-secret Encryption (GCHQ) vs RSA" ...


2

How do I find the co-efficient of $x^k$ in the expansion of $f(x)$? $$f(x)=\prod_{i=1}^3 (x+H(i))^i$$ Using Wolfram Alpha try online $$f(x) = (H(1) + x) (H(2) + x)^2 (H(3) + x)^3$$ and an see the expanded form there. This is a one-time job. If the $H$ is defined can be shortened, too. The $H(i)$ values should be reduced into $\pmod p$ before ...


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

Yes, field operations may involve numbers that are larger than the order. Public key point coordinates may exceed the order. Parts of the protocol that handle scalars work modulo the curve order, while the parts that handle elliptic curve points work modulo the prime modulus. Sometimes, as you noted, some information "crosses" between these domains:...


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

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.


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

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

There are not any secrets(except the output of course), the idea is to have a function that just uses multiplication (and maybe addition) and mod (no comparisons/if's) to have an unpredictable outcome when run over a large amount of iterations, like hashing hashes for N times If you are ok with there being "one secret" (although you do not need to ...


1

The (full) extended Euclidean algorithm is best expressed as a single loop with 6 variables in addition to inputs Input: polynomials $a$ and $b$ with $a\ne 0$. Setup: $(r,\hat r,s,\hat s,t,\hat t)\gets(a,b,1,0,0,1)$ Invariant: $a\,s+b\,t=r$ and $a\,\hat s+b\,\hat t=\hat r$ Loop: while $\hat r$ is not $0$ $q\gets r/\hat r$ $(r,\hat r)\gets(\hat r,r−q\,\hat ...


1

Can Eve break it if she can solve Diffie-Hellman problem? Yes, at least, the computational Diffie-Hellman problem. This problem is "given the triplet $h, h^x, h^y$, recover $h^{xy}$" Let us assume that Eve has an Oracle that solves this problem. Then, she sets $h=m^{ab}$, $h^x = m^b = (m^{ab})^{a^{-1}}$ and $h^y = m^a = (m^{ab})^{b^{-1}}$, and passes $h, ...


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