# Questions tagged [modular-arithmetic]

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

318 questions
Filter by
Sorted by
Tagged with
29 views

### How to solve polynomial modular equation to create a correct decryption algorithm

I recently had a variant of the following problem in my cryptography course and I had trouble solving it and was looking to get some help. Given the symmetric key cryptosystem: $\text{KG, Enc, Dec}$ ...
86 views

### Constructing an integer with specific totient without factorization

Given $N(=pq)$, but not its factorization. Somehow you manage to know, that $k$ divides $\phi(N)$. Is it possible to come up with an integer $N^{*}$, for which $\phi(N^{*})=\phi(N)/k$, without ...
104 views

### How to find the inverse of a polynomial in NTRU-PKCS

I am coding a java based implementation of the NTRU public-key cryptosystem. I can comprehend the majority of the algorithms involved in the encryption and decryption process well enough, but the key ...
63 views

81 views

### Extracting modulus from hidden function

I have a hidden function $f(x) = x \pmod{n}$ and would like to solve for $n$ based on a set of input and output pairs which can be chosen freely. I would like to do this without brute force (i.e. ...
102 views

### Finding a pair of exponents so that $c^a \bmod N = c^b \bmod N$

I am not very familiar with RSA, so this question may appear to be stupid. Suppose that in RSA encryption, we are given $c$ (the ciphertext) and $N$ (the semi-prime modulus), can we find a pair of ...
51 views

34 views

### GCD in Montgomery arithmetic

Wikipedia article on Montgomery modular multiplication contains the following statement: Many operations of interest modulo $N$ can be expressed equally well in Montgomery form. Addition, ...
65 views

### RSA-CRT exponent reduction

In the implementation of RSA-CRT, the exponent d is reduced mod p-1 ($d_p = d \bmod {(p-1)}$). The only proof I've found for that, is the following (considering $d = k\varphi(p) + d \bmod {\varphi(p)}$...
47 views

### EC threshold private key's multiplicative inverse and derived-key sharing

I have two devices, and each has a private key xPriv-i. Each device computes the corresponding EC public key xPub-i, shares it, and the linear combination of the keys is the "real" public key xPub. ...
52 views

### Relationship between special RSA modulus and quadratic residue in CL (Camenisch-Lysyanskaya) signature

I'm studying the CL(Camenisch-Lysyanskaya) signature (A signature scheme with efficient protocol proposed by Camenisch-Lysyanskaya). However, I cannot understand ...
66 views

325 views

I am given this question: Suppose Alice is using the ElGamal Signature scheme with parameters $p = 31847$, $\alpha = 5$, and $\beta = 25703$ Assuming that we have received signed messages $(x_1,(\... 1answer 202 views ### How does the squeeze function in the NaCl Poly1305 implementation work? The NaCl ref implementation of the Poly1305 algorithm uses the following reduction function (which is called squeeze()): ... 1answer 288 views ### How can I exploit the structure of the secp256k1 prime for fast arithmetic? I'm implementing logic on an FPGA (programmable chip) that does the key verification part of ECDSA on the curve secpk256k1, in which all operations are mod p where$p = 2^{256} - 2^{32} - 2^9 - 2^8 - ...
60 views

I'm studying about Additive differential of XOR I saw two papers that are "H.Lipmaa et al., On the Additive Differential Probability of Exclusive-or" and "V.Velichkov et al., The Additive ...