Modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" upon reaching a certain value… the modulus.

learn more… | top users | synonyms

2
votes
0answers
38 views

Recover secret $x$ when $c\equiv m^x \pmod p$ with public $p$ (modified)

Given an encryption system where $c\equiv m^x \pmod p$, $p$ is a known prime, 1. Is it possible to recover $x$ with a known plaintext attack? Given $(p,\text{factorization of }\varphi(p),m,c)$ 2. Is ...
1
vote
0answers
53 views

What can I do to improve my encyption method [closed]

I'm new to cryptography and I want to learn more. For me, the best way to learn about something that I have no experience with is to experiment and I've coded a very basic approach to a simple ...
-1
votes
1answer
77 views

NIST PRIMES - cryptography

I have a problem, If I have $p = \text{P-192} = 2^{192} - 2^{64} - 1$ with the base $2^{64}$ so, $2^{192} \equiv 2^{64} + 1 \pmod p$ the same that $(p=\text{P-192})$ or $2^{256} \equiv 2^{128} + ...
4
votes
3answers
113 views

Is there any alternative for extended euclidean algorithm to perform modulo division?

I'm implementing point addition and point doubling operations for elliptic curve cryptography. I have implemented extended euclidean algorithm to perform modulo division. It appears the that ...
5
votes
1answer
145 views

Modular exponentiation on calculator for textbook RSA

How do you encrypt $51$ with public key $(n,e) = (91,23)$ I understand that $c = 51^{23} \bmod 91$. How can I calculate the result on a calculator?
1
vote
2answers
51 views

Clarification regarding multiple modular exponentiation

If the base is same and exponents are different, for example: $R_1=b^x\bmod{p}$; $R_2=b^y\bmod{p}$; $R_3=b^z\bmod{p}$; ($p$ is large prime (2048 bit); $x$, $y$ and $z$ - 160 bit integers)) To ...
3
votes
2answers
181 views

Why are some x-coordinates unsuitable for an ECDSA generator point?

For Bitcoin's ECDSA curve (secp256k1, where $a=0$, $b=7$), why can't the generator point's first coordinate be $x=0$? That is, the point on the curve would be $(0,y)$ where $y$ satisfies $y^2 = 0^3 + ...
1
vote
1answer
153 views

Modular Arithmetic in RSA

Consider the following the following RSA public key $pk = (N, e) = (1457, 1307)$. (a) Knowing that $187^2 \equiv 1 \pmod {1457}$ find the factorization of $N$. (b) Given the factorization of $N$ ...
3
votes
1answer
65 views

How to perfrom modular division while numerator is lesser than the denominator?

I'm implementing point addition and point doubling of elliptic curve cryptography. The formula that I'm using for slope is Point addition: $S = \frac{(P_y-Q_y)}{(P_x-Q_x)}$ where $P$ and $Q$ are the ...
0
votes
0answers
44 views

what is the fastest and efficient method to perform modular multiplication?

I'm working on a code that needs to perform modular multiplication of big numbers several times. Since the operation takes place several times, using division to find the remainder is very expensive. ...
3
votes
2answers
125 views

Why does the modulus of Diffie–Hellman need to be a prime?

I read a lot about Diffie-Hellman, but there is one thing I dont understand: why does the modulus p need to be a prime? What if it would not be a prime?
1
vote
0answers
64 views

Does the RSA algorithm use repeated squaring?

Simple question: in order to reduce such huge exponents in modular arithmetic, is repeated squaring used in RSA or is there a better way to implement it?
2
votes
1answer
96 views

RSA: must $d$ be an integer?

I am only taking baby steps in RSA. If $p=11$, $q=7$ and $e=3$, $$\phi(n) = 10*6 = 60$$ Then: $$d = (2 (\phi(n)) + 1 ) / 3 = 121/3$$ Should $d$ be kept as a non-integer or is such a $d$ invalid? ...
1
vote
0answers
18 views

Probabilistic Disjoint Verification [closed]

Let $r_1,...,r_n$ be routers in the same organization, and let $h_{CO}$ be the least significant 32 bits of the hash of data packet $CO$. Router $r_i$ verifies $CO$ if $h_{CO} ≡ i \bmod n$. Assuming ...
5
votes
1answer
2k views

Which one is fastest? Karatsuba or Montgomery multiplication?

Is there any complexity analysis between Karatsuba and Montgomery multiplication algorithms? It seems that Karatsuba is more general in the sense that is not modulo tuned while Montgomery it is. Does ...
0
votes
2answers
46 views

Why do $\alpha$ and the private key value in diffie-hellman should be from $2$ to $p-2$

I just started learning Diffie-Hellman Key Exchange. I couldn't get the reason of making $\alpha$ and private key for Alice and Bob constrained between $2$ and the prime number generated minus $2$ ...
1
vote
1answer
43 views

Is it possible to get my x,y coordinates from my “secret exponent”?

...or is that possible? I am very new to cryptography! But, I think it's very interesting!! I have autism and numbers "are my thing" :) I already understand a couple of things. For example I know ...
0
votes
1answer
37 views

Modular arithmetics in diffie-hellman

Studying the basics of Diffie-Hellman key exchange, I'm stuck at a basic operation used in the end of the key exchange (where you show that both computations actually are the same). Can someone ...
2
votes
2answers
88 views

Is it possible to recover an RSA modulus from its signatures?

Let's say that you have some small number of RSA signatures of known data: you know some pairs $(m_k, c_k)$ such that ${c_k}^e \equiv m_k \pmod n$. If you know $e$, because probably it's one of $\{3, ...
2
votes
2answers
43 views

What is the correct way to notate elliptic curve properties

When looking through elliptic curve and modulus posts i can see many examples of people referencing $p$ and $n$, in upper and lower case, and sometimes $Q$ is written instead of $p$ or $P$, and I ...
2
votes
0answers
44 views

Discrete logarithms: large prime modulus vs. large semi prime modulus

I have a cryptography homework question, in the question it says a cryptographic hash function in the form of $f(x) = g^x \bmod n$ , where $n$ is a very large prime (1024bits and more), $g$ is a ...
5
votes
2answers
180 views

lcm versus phi in RSA

In textbook RSA, the Euler $\varphi$ function $$\varphi(pq) := (p-1)(q-1)$$ is used to define the private exponent $d$. On the other hand, real-world cryptographic specifications require the ...
0
votes
2answers
52 views

How hard to solve the given mod problem

Let c = a.b mod p where p is n bit prime number (e.g. 128 or 160 bit prime number); a - random number between 1 and (p-1); b - random number between 1 and (p-1); Given c, a and p, how hard to ...
6
votes
3answers
191 views

Is there an upper bound to the private exponent in RSA?

In the RSA algorithm, we choose $p$ and $q$ as prime numbers and we select a value $e$ which is coprime to $\varphi(pq)=(p-1)(q-1)$. Then we calculate $d:=e^{-1}\bmod\varphi(pq)$. My question is: ...
4
votes
3answers
134 views

Calculating $\mathbb F_{p^2}$-rational points of an elliptic curve defined over $\mathbb F_p$

How can I calculate points on an elliptic curve defined over $\mathbb F_p$, for example $y^2 \equiv x^3 + 1 \pmod p$, with coordinates in $\mathbb F_{p^2}$? (points might have complex number format in ...
3
votes
1answer
86 views

How to understand RSA Proofs of correctness at Wikipedia

From Wikipedia(https://en.wikipedia.org/wiki/RSA_%28cryptosystem%29#Proofs_of_correctness): $m^{ed}$ ≡ $m$ $\pmod{q}$ $m^{ed}$ ≡ $m$ $\pmod{p}$ then $m^{ed}$ ≡ $m$ $\pmod{pq}$ Question: if $m^{ed}$ ...
5
votes
1answer
213 views

Using same modulus for RSA

I know that there exist some attack when using same modulus. Can two different pairs of RSA key have the same modulus? RSA cracking: The same message is sent to two different people problem But ...
2
votes
1answer
41 views

Requirements for the modulus in the Massey-Omura three pass protocol

In the Massey-Omura three pass protocol: How many bits long should the prime modulus $M$ be in order to be secure? Should the $M$ be secret? Should the $M$ be generated every time or it could be ...
2
votes
1answer
79 views

In $\mathbb Z/p\mathbb Z$, is $(a+b\cdot r)$ a random value for fixed $a,b$ and random $r$?

Let $p$ be a prime number. Consider two fixed values $a,b\in\mathbb Z/p\mathbb Z$, where $b\neq0$, and a uniformly random value $r\leftarrow \mathbb Z/p\mathbb Z$. Is $v=a+b\cdot r$ a uniformly ...
1
vote
1answer
90 views

Modular reduction for NIST prime P256— understanding the data

I am working on a project where I need to implement elliptic curve cryptography, I am struggling from a long time in order to understand the working and the process. Modular finite field arithmetic, ...
3
votes
1answer
104 views

Base point in Ed25519?

The paper "High-speed high-security signatures" by Bernstein et al. introduces the Edwards curve Ed25519. Concerning the base point $B$, it says that $B$ is the unique point $(x, 4/5)\in E$ for ...
0
votes
0answers
41 views

RSA Encryption: What happens if n is a factor of the message M? [duplicate]

From what I have learned about RSA encryption, the message M and the modulo n must be coprime because Euler's theorem only holds for coprime numbers? for example, what happens if I choose p = 3, q = ...
5
votes
2answers
781 views

Understanding elliptic curve encryption [closed]

I'm having a hard time understanding the elliptic curve encryption. One thing thing I don't understand is listing all the points on the curve mod p. Suppose I have the following elliptic curve: $y^2 = ...
1
vote
1answer
225 views

How does knowing the factorization of N help to obtain the secret?

Assuming $x=a^2 \pmod n$ and knowing $x$, $p$, $q$ how is it possible to obtain $a$?
13
votes
1answer
15k views

Calculating RSA private exponent when given public exponent and the modulus factors using extended euclid

When given $p = 5, q = 11, N = 55$ and $e = 17$, I'm trying to compute the RSA private key $d$. I can calculate $\varphi(N) = 40$, but my lecturer then says to use the extended Euclidean algorithm to ...
3
votes
2answers
117 views

What is the difference between the standard representants of $\mathbb Z/q\mathbb Z$?

The symbol $\mathbb Z/q\mathbb Z$ (given that $q$ is prime) represents the prime field $\mathbb Z_q$. Basically, the elements of this field are represented by $\{0, 1, \dots, q-1\}$, let's call this ...
0
votes
1answer
83 views

Working on subgroup of $\mathbb{Z}^*_p$ in practice

It is said that, given a group $\mathbb{Z}^*_p$, we can always have a subgroup whose order is prime. To this end, for a safe prime $p=2q+1$, compute $x_i^2 \bmod p$ for all $x_i \in \mathbb{Z}^*_p$. ...
0
votes
1answer
65 views

RSA function over $Z_t^{*}$ where $t$ is prime

RSA function is defined over $Z_N^{*}$ where $N=pq$ with $p,q$ primes. A public key is a pair $(N,e)$ and a private key is $(N,d)$ where $d=e^{-1} \mod \phi(N)$. Assume that RSA function is defined ...
3
votes
0answers
84 views

What happens if no final subtraction is done in Montgomery multiplication?

I'm doing Montgomery arithmetic modulo $N = 2^{255}-19$ for the Curve25519, picking $R = 2^{256}$ for Montgomery. After multiplying two numbers $0 <= A,B < N$ in the Montgomery representation ...
2
votes
3answers
341 views

Point decompression on an elliptic curve

I'm programming an elliptic curve cryptosystem and I'm having difficulty with decompressing points. The following information is from my project specification as to my understanding: Given a point ...
2
votes
0answers
141 views

Proxy re-encryption mod operations

I managed to implement the proxy re-encryption scheme from http://eprint.iacr.org/2009/189.pdf in Python 2.7, however I am having performance issues. As it is, I can run the algorithm for key sizes up ...
-1
votes
1answer
98 views

Montgomery and Galois fields

I'm a little bit confused about the design of a RSA module in VHDL. My question isn't directly related to hardware design. I've read a lot of publications and I bought also a book. In one publications ...
1
vote
1answer
164 views

Montgomery Algorithm

I'm trying to undestand how it works and how to implement the algo described in this paper. The paper shows a methods to compute a modular multiplication where it is used multiplier with a resolution ...
1
vote
1answer
244 views

Solving a quadratic equation for a variant of Rabin

My understanding of Rabin We have $p$ and $q$ which are distinct primes congruent to $3 \pmod 4$. Then we have $n = pq$. Encryption is done as $e(m) = m^2 \pmod n$, where $m$ is our message. ...
3
votes
3answers
215 views

Attack against modular inversion operation using side-channels?

I'm building a device that performs a modular inversions using a secret modulus. I would like to know if it is possible to recover all or part of this modulus by side-channels (timing, power, EMR, ...
3
votes
1answer
249 views

How is information disclosed by modular multiplication?

Consider the case that $c = a \cdot b \mod p$ where $p$ is a known prime and $0 < a < p$ and $0 < b < p$ are unknown integers numbers. Furthermore, some bits on the value of $c$ are ...
0
votes
0answers
60 views

Bilinear pairing arithmetic - cryptographic accumulators

For calculating accumulated values for set of elements chosen randomly from say $ { e_1 ,e_2,...e_n}\varepsilon X $ we use the formula $acc= g^{f(e,s)}$ where $ f(e,s)= (e_1+s)(e_2+s).....(e_n+s)$ ...
1
vote
1answer
176 views

How to calculate RSA CRT parameters from public key and private exponent

Given the public key (n, e) and private exponent (d), how to calculate CRT parameters (p, q, dP, dQ, and qInv) of this RSA key pair?
7
votes
2answers
3k views

In RSA, why is it important choosing e so that it is coprime to φ(n)?

When choosing the public exponent e, it is stressed that $e$ must be coprime to $\phi(n)$, i.e. $\gcd(\phi(n), e) = 1$. I know that a common choice is to have $e = 3$ (which requires a good padding ...
0
votes
0answers
44 views

Factorization of a number obtained by a modular multiplication operation can reveal factors of the used operands?

Consider a number $r$ obtained by: $r=a \cdot b \mod n$ Can knowing the factorization of $r$ reveal some information (bits) of $a$ and $b$ ?