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

0
votes
1answer
60 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
57 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 ...
2
votes
0answers
72 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
238 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
42 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)$ ...
0
votes
1answer
45 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
42 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
40 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
44 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 ...
0
votes
1answer
73 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
63 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!
1
vote
1answer
50 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
71 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 ...
1
vote
3answers
111 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
72 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?
0
votes
1answer
198 views

How does knowing the factorization of N can 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
52 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 ...
4
votes
1answer
90 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
77 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 = ...
1
vote
1answer
82 views

Finding $x$'s parity in the discrete log problem

Suppose $p$ is prime, and $g, a\in\mathbb F_p$ are given elements with $g$ a primitive root. The discrete log problem poses the task of finding an integer $x$ such that $g^x=a$. Show that even if $x$ ...
0
votes
0answers
25 views

Reducing key shares in Damgård-Dupont threshold RSA

I'm working on understanding and implementing Damgård, I., & Dupont, K. (2005). Efficient Threshold RSA Signatures with General Moduli and No Extra Assumptions. Public Key Cryptography-PKC ...
-1
votes
1answer
88 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 ...
2
votes
2answers
145 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 + ...
2
votes
2answers
91 views

Formal security of recycled random blinding in a Paillier scheme

This question is a follow-up/variant on a previous question. Supposing that we are trying to generate a large number of (indistinguishable) ciphertexts of a given plaintext and want to avoid the ...
1
vote
1answer
65 views

How bad would it be to reuse the random blinding factor in a scheme like Paillier?

A secure and somewhat fast way to "re-encrypt" (refresh? anonymise?) a Paillier ciphertext, $c$, is to multiply it by an exponentiated random value: $c \gets c \cdot r^n \mod n^2$ (with $r \in ...
1
vote
3answers
115 views

Programming language for modular arithmetic over large numbers [closed]

I'am trying to implement algorithms on integer factorization.This involves dealing with integers of 200-500 digits and doing modular arithmetic over them.Which programming language has inbuilt support ...
1
vote
1answer
143 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
votes
1answer
122 views

subgroup of quadratic residue

if a number is said to be a subgroup of a quadratic residue of Z∗p, can I affirm that it is a generator of a cyclic group ? ie, say i am looking for a number which is an element of order q in Z*p, ...
0
votes
3answers
229 views

Random Galois fields

Note: I have now answered this by my own research and can generate random fields up to G(2^9) in reasonable time. I would need to find more speedups for larger fields. At this time G(2^8) takes a few ...
0
votes
0answers
118 views

RSA - Why should we sign hash rather than raw content? [duplicate]

Apart from obvious performance considerations, is there any mathematical or crypto reasons that imply that we sign a hash rather than a raw content ? I read that it was because the hash must fit in ...
3
votes
2answers
93 views

Security concern about reducing hash value using modulo operation

As stated in the title, what I am looking for is information about a "technique" that I would like to use in some of my algorithms. Sometimes I need to map a hash function's result into a range of ...
0
votes
1answer
84 views

Modular Reduction of polynomials in GF(2^m)

Hello I am having trouble understanding the algorithm implementation in hardware of the reduction process over galois fields of F(2^163) In the following process it ...
2
votes
1answer
70 views

For which RSA moduli, precisely, is $e=d$ for all $e$?

This question shows that there are at least two valid RSA moduli $n$, namely $35$ and $91$, such that for any $e$ coprime to $\lambda(n)$, $$e^2\equiv1\mod\lambda(n)\text.$$ Reading the linked ...
1
vote
1answer
118 views

Polynomial division hardware implementation

I am beginning the implementation of the polynomial binary division algorithm now as I understood i will be checking the MSB bit if 1 to XOR and shift the sum if 0 i will only shift. What I am not ...
0
votes
1answer
78 views

Polynomial Modulus

So I am studying for finals and I came across this problem and I am completely stuck. I would really appreciate someone to clarify on the steps to take to solve these problems. Let $f(x) = x^4 + x^3 ...
1
vote
1answer
76 views

Fermats Little Theorem, primitive root [closed]

So I am studying for finals and I am not able to solve the problem: Let $ p = 3 * 2^{11484018}- 1 $ be a prime with 3457035 digits. Find a positive integer $x$ so that $2^x\equiv 3\pmod p$ Any ...
0
votes
0answers
73 views

Polynomial Inversion over Galois Field

Hello guys I am looking to calculate the Inverse of a given polynomial in Galois field I have found the little Fermat's algorithm and the Itoh-Tsujii I am getting a bit confused with both algorithm ...
2
votes
1answer
100 views

Roots in modulo field

I have a point $(X,Y)$ on an elliptical curve $E(a,b)$ where $a=-3$ and $B$ is a large number that is in hexadecimal from -51BD. To compress this point oficially in a program, we know that every $X$ ...
1
vote
1answer
48 views

Modulo Square Roots [duplicate]

Here's my issue and someone can help me understand it so I can program it correctly. I have a point(X,Y) on an Elliptical Curve E(a,b) where a=-3 and B is a large number that is in hexidecimal from ...
1
vote
1answer
77 views

Arithmetic modulo 1

In the context of lattice-based cryptography, in particular the Learning With Errors (LWE) problem, I see some definitions given in terms of equations modulo 1 (see for example, Appendix A of this ...
1
vote
3answers
204 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 ...
0
votes
1answer
153 views

Addition / Multiplication modulo 13

I am currently studying Diffie-Helman protocol. In my lecture notes I have a generator g=2 and I'm in group $Z_{13}^*$ . There I calculate a remainder cycle from 1 to 12 with $r =g^i \mod 13 \forall ...
0
votes
1answer
188 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. ...
2
votes
1answer
242 views

Square roots, prime factorization

I´m stuck in my homework and since its homework, I would rather get some hints than full solution. The problem goes: factorize n = 88416763 in case that you know that the square roots of 51733469 ...
0
votes
1answer
84 views

Showing that $2^{N-1}\equiv1\pmod N$ when $N=2^p-1$ for prime $p$

I got this question on a previous exam and I got it wrong. I've gone back through it several times since then, but I can't seem to get it. I would really like to know how to do it, so if someone could ...
1
vote
2answers
105 views

RSA prove $a^{\varphi(n)/g} \equiv 1 \pmod{n}$

I should prove that $a^{\varphi(n)/g} \equiv 1 \pmod{n}$, so I thought I would prove it with primitive roots but I got stuck. Here is the assignment: Let $p, q$ be primes such that $p \ne q$. ...
3
votes
2answers
764 views

Reversing DJB2 Hashes

I have some spare time, and a few hundred DJB2-hashed values sitting around. I thought I'd try to do something "useful" and invert DJB2, such that I could calculate the plaintext of the hashes (which ...
5
votes
3answers
663 views

RSA with modulus n=p²q

I've been wondering what would happen if the RSA modulus would be $n=p^2q$ instead of $n=pq$. I feel like there is an obvious security flaw (as there is with most modifications). Would this choise of ...
2
votes
3answers
323 views

In RSA, why does $p$ have to be bigger than $q$ where $n=p \times q$?

In openSSL – during RSA key generation – if $q$ is bigger than $p$, they exchange them. Why is that?
4
votes
2answers
401 views

Exactly two of the four roots must be greater than N/2

Theorem: Let $y$ be a quadratic residue in $\mathbb{Z}_N$* where $N=pq$. There are exactly four integers $x_1, x_2, x_3, x_4$ where $0 < x_1 < x_2 < \frac{N}{2} < x_3 < x_4 < N$ ...