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

Filter by
Sorted by
Tagged with
1 vote
0 answers
60 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 \...
1 vote
0 answers
21 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, ...
0 votes
1 answer
33 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
242 views

RSA and Wiener's attack [closed]

I'm trying to do Wieners' attack for the case \ ...
1 vote
2 answers
51 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 ...
  • 593
1 vote
0 answers
107 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 ...
  • 1,990
1 vote
0 answers
429 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 ...
1 vote
0 answers
56 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
289 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
229 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
272 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 ...
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
6 votes
2 answers
7k 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?
  • 143
3 votes
1 answer
296 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 ...
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://...
3 votes
2 answers
419 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,883