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
2 votes
1 answer
59 views

About Naccache-Stern higher residue cryptosystem definition

About the Naccache-Stern cryptosystem, I have found two different encryption algorithms: In the original paper from Naccache and Stern, the encryption step is performed by calculating $c = g^m \...
hectorvr14's user avatar
1 vote
0 answers
46 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 ...
Puneet Jain's user avatar
1 vote
1 answer
394 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:...
Ayumi80s's user avatar
1 vote
0 answers
91 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 \...
Jakab Martin's user avatar
1 vote
0 answers
25 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, ...
Robert Huang's user avatar
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: ...
Jan's user avatar
  • 53
0 votes
1 answer
383 views

RSA and Wiener's attack [closed]

I'm trying to do Wieners' attack for the case \ ...
Anonymous's user avatar
1 vote
2 answers
54 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 ...
Bean Guy's user avatar
  • 742
1 vote
0 answers
135 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 ...
hardyrama's user avatar
  • 2,126
1 vote
0 answers
460 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 ...
Antoshka's user avatar
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 ...
JeWe37's user avatar
  • 11
-1 votes
2 answers
318 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 ...
Mithun Ogawa's user avatar
3 votes
0 answers
253 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 ...
mbuke's user avatar
  • 31
0 votes
1 answer
285 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 ...
Tom Corless's user avatar
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,...
Gravian's user avatar
  • 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 ...
Bob's user avatar
  • 1
8 votes
2 answers
9k 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?
Kiran's user avatar
  • 183
3 votes
1 answer
370 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 ...
user17140's user avatar
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://...
user11886's user avatar
3 votes
2 answers
427 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$ ...
user5507's user avatar
  • 1,913