# Tag Info

1

If you want to reduce integers modulo that specific prime (and I assume you have checked whether $p = 2^{256}-2^{32}-2^9-2^8-2^7-2^6-2^4-1$ is prime or not), I would suggest you don't use the Solinas algorithms, but instead a different one geared towards modulii of the form $2^n - c$ for small $c$. The identity underlying this operation is actually fairly ...

1

There's a much simpler way to factor $n$ when you know $d$ at least when $e$ is small (like when it is usually 65537). You know that $ed = 1 \, (\textrm{mod} \,\phi)$. Since you know $e$ and $d$ you can calculate $S = ed - 1$ and this number must be divisible by $\phi$ due to the first equation. Note that the magnitiude of this value is around 65537 times ...

4

I had a similar problem, and it took me a long time to figure out all the math, as some of the proofs can be rather terse. So, I took it upon myself to write a full explanation of how to factor N, without all the symbols and relying on a bit less prior knowledge. Anyway, such a system is not safe. If you know a valid $e$ and $d$, you can factor $N$. ...

3

Do you want DDH/RSA-based PRFs? If so, we have them and I will answer. – xagawa @xagawa Yes, I want that :-) – Dingo13 I list the PRFs based on the number-theoretical assumptions. They are arithmetic or mathematical function.'' You can use the Feistel network to obtain (S)PRPs from PRFs in theory. From the DDH assumption The Naor-Reingold ...

1

I don't have a full answer yet but here is what I have so far. Since you know what $p^5 \bmod N$ is and what $q^5 \bmod N$ is then you know what $m^5 \bmod N$ is. Since we also know what $N$ is then we should be able to find out how many times we need multiply $m^5 \bmod N$ by $m^5 \bmod N$ till we get a full cycle (you can calculate it through $\phi(N)$ or ...

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

-1

No. Conceptually , not so strongly close but similar ones that would come closer is $k$-wise Independent Distributions/Functions .

0

Why not use Fermat's Little Theorem to calculate your inverse instead? ie $$a^{phi(m)-1}=a^{-1}\mod{m}$$ Although this would require repeated squaring (which is also vulnerable to side channel attacks) the number you would obtain from any attack would be the exponent, not the thing you were calculating the inverse of. As you would have already given ...

2

Whenever you're trying to attack a scheme that is [algebraically] relatively simple like this one, a sensible first step is to write out everything you know. Now, considering the information you've been given, try and substitute things into oneanother, and see where this leads you. Let $(m,c)$ be the first 1024 bits of the plaintext-ciphertext pair. Now, ...

Top 50 recent answers are included