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
57 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
78 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} + ...
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 ...
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 ...
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. ...
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$ ...
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 ...
1
vote
0answers
65 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?
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 ...
3
votes
2answers
128 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?
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 ...
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 ...
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 ...
3
votes
1answer
87 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}$ ...
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: ...
5
votes
1answer
214 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
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
91 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, ...
4
votes
3answers
135 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
105 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 = ...
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 ...
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 ...
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
178 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?
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$ ?
0
votes
1answer
72 views

How to perform homomorphic multiplication in ElGamal?

How can I compute homomorphic multiplication in ElGamal? That is: Given two ciphertexts $(R_1,c_1)$ and $(R_2,c_2)$ corresponding to plaintexts $m_1$ and $m_2$ under some public key; how can I compute ...
0
votes
1answer
96 views

RSA: How to calculate the private exponent?

I have this problem: In RSA algorithm considering $n=33$ (modulus) and public exponent $e=3$, calculate the corresponding private exponent $d$. I know that $d = e^{-1} \pmod{\varphi(n)}$ and ...
1
vote
1answer
255 views

RSA modulus (N) from public key and calculating N from p, q not equal [closed]

I have a RSA public key in the form of public exponent and modulus as follows: ...
1
vote
1answer
108 views

algebraic attacks for mixed operations (mod 2 and mod 256) [closed]

If a cipher has mixed operations, e.g $\oplus$ (addition mod $2$), and addition modulo $2^8$. How we we going to express them mathematically? Thanks in advance!
2
votes
1answer
60 views

Average/approximate difference in value between valid consecutive $x$ coordinates in ECC?

From my basic understanding not all values of $x$ coordinates can satisfy a given elliptic curve equation, i.e. some $x$ coordinate values are not valid points on the curve because $x^3+ax+b$ is not a ...
0
votes
1answer
78 views

RSA weak padding

Suppose to have a function for numbers expressed in 8-bit $\in [0,2^8-1]$ defined as: $$f(x)=x||x||x||x$$ where $|f(x)|$ is exactly 32 bits. e.g., suppose x=2 (00000010) so ...
2
votes
3answers
143 views

How does $g$ being a generator imply Diffie-Hellman's correctness?

In the Diffie-Hellman protocol for key exchange over an unsecured channel, we choose $p$ and $g$, where $g$ is a generator of $\mathbf{Z}_p^*$. However I want to know why this assumption makes the ...
0
votes
2answers
81 views

Would the Fiat Shamir identification scheme be more secure if I design it with an exponents higher than 2?

Let's say both Prover and Verifier would use nth power instead of 2nd when creating public keys and when verifying. I know it would slow it down but would that cause the protocol to be more secure?
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$?
-1
votes
3answers
56 views

Reduction of a modular exponentiation's base does not change the result

Can anyone help me to prove this property used in the RSA correctness theorem? $a^b\bmod{n}\equiv (a\bmod{n})^b\bmod{n}$ Specifically, here is what I have done: this is what i mean. i can't ...
6
votes
1answer
114 views

What are the computational benefits of primes close to the power of 2?

Recently I was reading some article about the Bernstein's Curve25519. This is a particular Montgomery curve over $\mathbb{F}_q$ where $q = {2^{255}-19}$. What I missed or was unable to understand is ...
0
votes
0answers
117 views

Deriving a decryption equation

Consider a very simple symmetric block encryption algorithm, in which 32-bits blocks of plaintext are encrypted using a 64-bit key. Encryption is defined as C = (P⊕KL)⊗KR where C = ciphertext; K = ...