Questions tagged [congruence]
If two numbers $b$ and $c$ have the property that their difference $b-c$ is integrally divisible by a number $m$ (i.e., $(b-c)/m$ is an integer), then $b$ and $c$ are said to be "congruent modulo $m$."
19
questions
1
vote
0
answers
41
views
Determining the Parity of Exponent b in Modular Exponentiation Given Three Known Values
I have three numbers x, a, and c, where both a and c are odd numbers. The number x is the output of the following function:
$$
x = a^b\!\!\!\!\!\!\!\mod{c}
$$
I am attempting to determine whether the ...
- 11
1
vote
1
answer
257
views
Solve congruent equation likes N = p*q c1 = (2*p + 3*q)**e1 mod N c2 = (5*p + 7*q)**e2 mod N
Here is a CTF crypto challenge likes(its write up is public on https://ctftime.org/writeup/15438):
$$N = p*q\\
c1 = (2*p + 3*q)^{e_{1}} mod N\\
c2 = (5*p + 7*q)^{e_{2}} mod N$$
After i transform these:...
- 23
1
vote
0
answers
82
views
What is the proof that the RSA is collision-free?
We have the RSA function:
$c = m^e (mod n)$.
I would like to know the proof that there is not an $m_1$ and an $m_2$ message that produce the same $c$.
My thoughts:
We know that $m \le n$, so $m_1 \...
- 11
1
vote
0
answers
24
views
Possible plain text needed on a congruence modulo - based encryption
Suppose m is a positive integer converted from the plain text in bytes.
And there are two positive integers a, ...
- 11
0
votes
1
answer
35
views
Congruence in the Schnorr identification scheme
I have been looking at the Cryptography: Theory and Practice book by Stinson and Paterson and when I came to the Schnorr identification scheme, I read the sentence that goes something like this:
...
- 53
0
votes
1
answer
334
views
1
vote
2
answers
52
views
What exactly means to sample from the set of congruence classes?
Say one is doing some cryptography around the set of congruence classes, namely: $$\mathbb{Z}/n\mathbb{Z} = \mathbb{Z}_n = \{[0]_n, [1]_m, \dots, [n-1]_n\}.$$
Sometimes we use to write $a \leftarrow_R ...
- 722
1
vote
0
answers
126
views
RSA congruence (n is not given) [closed]
it might be a silly question but i need help please
given RSA system , where $n=pq , p\ and \ q \ are \ primes $ , $ v_0,v_1,v_2, v_3 \ are \ known $
$p^p \equiv v_0 \mod q$
$q^q \equiv v_1 ...
- 2,074
1
vote
0
answers
454
views
How to get unknown constants from linear congruential generator
I need to crack this linear congruential generator.
I have
$$X_{n+1}=a⋅X_n +b \pmod m$$
I know: $m=31,X_3=30,X_4=19,X_5=26$
How can I find $a,b$ and $X_0$?
I have got already the following ...
- 11
1
vote
0
answers
57
views
Geometry of the outputs of linear congruential random number generators
I learned that possible $m$ long sequences produced by linear congruential random number generators(of the form $r_{i+1}\equiv ar_i+b \mod n$) fall on hyperplanes. Using this fact I have come to think ...
- 11
-1
votes
2
answers
299
views
A quick way to justify whether $a^m \equiv 1 \pmod{n}$?
Say I would like to justify whether $10^{28} \equiv 1 \pmod{29}$. I know according to Fermat's little theorem that $a^{p-1} \equiv 1 \pmod{p}$ when $a$ is a primitive root modulo $p$. What about ...
3
votes
0
answers
244
views
Finding the cycle sets of an LCG
My LCG has the form:
$$S_0 = k$$
$$S_{n+1} = S_n \times a + 1 \pmod m$$
Each choice of $k$ generates a different sequence but in some cases a sequence may just be a cyclic shift of another. In this ...
- 31
0
votes
1
answer
280
views
Inverting RSA using an oracle
Say you are given an efficient deterministic algorithm 'I' that can invert the RSA
function on 1% of the points in $Z^*_{N}$. That is to say that if y $ \in $ $Z^*_{N}$ is a "good" point for 'I', then
...
- 67
6
votes
1
answer
4k
views
Crack linear congruential generator knowing every other word in sequence
I need to crack one of the example of linear congruential generator.
I have $X_{n+1} = (a \cdot X_n + b) \bmod m$
and I know every other word in the output sequence:
..., 3158, ..., 1888, ..., 1285,...
- 95
0
votes
0
answers
94
views
Find a polynomial time algorithm for the following problem
Let $p$ be a prime number and let $c \in \mathbb{Z}_p$ and $e \in (\mathbb{Z}/(p-1))^{\ast}$. Put $c \equiv_p m^e$. Find a polynomial time algorithm that given $p$, $e$, and $c$ will compute $m$.
I ...
- 1
7
votes
2
answers
8k
views
Significance of 3mod4 in squares and square roots mod n?
Why do most literature while discussing squares or square root modulo a prime P, consider P to be congruent to 3 mod 4?
- 153
3
votes
1
answer
337
views
What's causing the poor randomness in this program: the LCG, or the program logic itself?
(Crypto Gods, I should begin by stressing that I haven't lost my mind: I'm not doing this in real life, I'm just trying to understand the theory behind what's happening. With your help, hopefully I ...
- 33
5
votes
2
answers
2k
views
Safe elliptic curve point addition using projective coordinates: How do I tell if the points are the same?
I am trying to implement elliptic curve point addition in hardware for NIST p256 and p384 curves. I have noticed the following issue with the suggested NIST routines:
Consider routine 2.2.7 of http://...
- 51
3
votes
2
answers
425
views
How can I solve congruence modulo N?
I am trying to solve congruences of the form
$$J_A \cdot a^e\equiv 1 \pmod n$$
where $n=pq$ for $p,q$ prime and $\gcd(e,\varphi(n))=\gcd(J_A,n)=1$
Solve for $a\in \mathbb{Z}$, in terms of $n,J_A$ ...
- 1,903