Modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" upon reaching a certain value… the modulus.
0
votes
0answers
40 views
Interpolate $(x_i,y'_i)=[(1,5),(2,1),(3,4)]$ with $\prod_{i=1}^n y'{_i}^\left(\prod_{\genfrac{}{}{0}{1}{j\not=i}{j=1}}^n\frac{x_j}{x_j-x_i}\right)$
I have three points $(x_i,y_i) = [(1, 9), (2, 20), (3, 37)]$ from a polynomial $3x^2 + 2x + 4 \pmod{11}$ where the secret $s=4$
And I would like to compute the constant $c=9$ to the power of the ...
-5
votes
1answer
40 views
One Time Pad OTP: with modular math, ciphertext reveals modulus always, yes or no?
Assuming that in the OTP scheme, the key has more values than the alphabet, then: using modular math predetermines that the highest possible value in the ciphertext will reveal the modulus used in ...
0
votes
2answers
116 views
OTP One Time Pad : How does modulus size greater than alphabet size eliminate perfect secrecy?
If my plaintext alphabet is {0,1,2}, it has three characters, and I understand why I cannot use a modulus less than 3 (decryption won't work).
My key has 100 different values, {0,1,2 .....99} . ...
2
votes
2answers
51 views
One Time Pad OTP : Optimal modular base per given plaintext space?
Background: my question at :
My pencil and paper One Time Pad works fine without modular math ...... or does it?
I am trying to understand, from a layman's point of view, how to make the best one ...
2
votes
1answer
32 views
choices for k in binary finite field modular reduction algorithm
In the Guide to Elliptic Curve Cryptography there's this algorithm:
My question is... what is $k$? Is it just some random value we pick? If so are some numbers better than others?
4
votes
1answer
215 views
RSA given d and d = p
Assume we have a somehow unorthodox implementation of RSA whereby:
$p$ and $q$ are chosen primes of length $n/2$ where $n$ is the number of bits desired in $N=p\,q$ and
$$\begin{align}
\phi &= (p-...
0
votes
1answer
31 views
Additive homomorphic encryption: strict equality - handling congruence
Is there an additive homomorphic encryption scheme which guarantees that if provided with
$E(v)$, $E(m_1)$ and $E(m_2)$
and $E(v)=E(m_1).E(m_2)$ then $v=m_1+m_2$
Please note this is not $v \equiv ...
1
vote
2answers
120 views
My pencil and paper One Time Pad works fine without modular math … or does it?
With no background in higher math or computer science, I could not quite grasp the value of modular math for simple OTP systems as described in other posts here.
I have an alphabet size of 40 ...
2
votes
2answers
45 views
Break large exponent calculation into smaller calculations?
I am implementing SRP on an embedded platform. It has crypto acceleration and I am using its built in modular exponentiation function, however it doesn't seem to be able to handle an exponent over 32 ...
1
vote
1answer
47 views
Computations in extended finite field p^2
I would like to construct a distortion map from a point $\in \mathbb{F}_p$ to $\mathbb{F}_{p^2}$.
If I have an elliptic curve $Y^2 = X^3 + 1$ over $\mathbb{F}_p$ and a distortion map $\phi(x,y) \...
1
vote
0answers
39 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 ...
4
votes
0answers
131 views
Indistinguishability vs fixed bit-length
Suppose there is a cyclic group $\mathbb{G}$ of prime order $q$ of elements in $Z^{∗}_p$ with a generator $g$ and values $a,b,c,d \in Z_q$.
There is also an equation $g^{ab} = g^{cd}$, where $a,b,c$ ...
0
votes
2answers
65 views
Public-key generation - primes reuse
Given the following Trap-door Commitment scheme
Secret key receiver: $x_B \in_u Z_q$
Public key receiver: $y_B = g^{x_B} \mod p$
Here, $p=q*k+1$ for two primes $p,q$ and $k \in Z$. And $g$ is the ...
1
vote
1answer
315 views
Paillier: guessing the message when knowing the cipher and the random number
I cannot get my head around this.
In Paillier, the ciphertext is calculated using
$c = g^m.r^n\ mod\ n^2$
where $(n,g)$ forms the public key and $r$ is a random number $0<r<n$.
Assuming an ...
0
votes
2answers
85 views
RSA: finding e given n, m and c
So I'm not sure if this is possible but assume I have
$$c \equiv m^e \pmod n$$
I have $c$, $m$ and $n$ but no $e$, which in my case I a value that can be up to 15 digits. Is there a way to do this?
0
votes
1answer
65 views
Is there a formula for calculating the inverse of a sum in modular arithmetic?
Suppose there is a cyclic group $G$ of prime order $q$ of elements in $Z_p^*$ with a generator $g$ and a value $x \in Z_q$.
$h_1 = g^{x+1}$
$h_2 = g^{x}$
Is it possible to write $h_2^{((x+1)^{-1})}...
5
votes
1answer
99 views
Why FHE takes modulo space $\Bbb Z_p$ as $[−p/2,p/2)$ rather than $[0,p)$?
Why doesn't FHE scheme see a modulus space $\Bbb Z_p$ as $[0,p)$ ?
Instead, it consider $\Bbb Z_p$ as $\left[-\frac{p}{2},\frac{p}{2}\right)$.
What's the concrete reason?
What happens if I use $[0,p)$...
-1
votes
2answers
146 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 ...
4
votes
1answer
175 views
Solving the discrete logarithm problem for a weak group
I was reading an answer about an attack on a weak group for the discrete logarithm problem and wanted to formalize and verify that the attack was correct. That is, that it was guaranteed to always ...
0
votes
0answers
26 views
Remainder of two large boolean Arrays (length>1024 bit)
I'm fairly new to cryptographic topics. At the moment I am failing at a "simple" task:
I want to compute
$x \bmod n$
with x and n beeing Boolean Arrays (representing integers) with size greater than ...
0
votes
0answers
38 views
Constructing System of Equations of Modular Subtraction, Modular Multiplication and XORS
This is a toy cipher. The design is inspired by a question (Solve System of Equations including XOR and Modular Addition), however the design involves different operations.
My cipher takes as input 2 ...
1
vote
1answer
81 views
Solve System of Equations including XOR and Modular Addition
A Dummy cipher is shown in figure below. Plaintext is 16 bits ($X_1$ and $X_2$ are 8 bit each). Ciphertext is computed after two rounds using two round keys $K_1$ and $K_2$. Can the round keys $K_1$ ...
4
votes
1answer
126 views
How can I determine if a hash function is secure?
I'm doing an exam in computer security and I encountered this problem which I'm unsure of how to attack properly. Should I get down and dirty with the Hash function on paper or is there a more general ...
1
vote
0answers
41 views
Algebraic Attack on Mix Mode Modular Arithmetic
I have a toy cipher that comprises of Mix Mode Modular Arithmetic (bit similar to IDEA including, Addition Modulo $2^{n}$ , Multiplication Modulo $2^{n}$ , Subtraction Modulo $2^{n}$ and circular ...
1
vote
1answer
39 views
Modifying Mix Mode Modular Arithmetic in IDEA Cipher
IDEA uses Mix Mode Modular Arithmetic that includes Addition Modulo $2^{16}$ and Multiplication Modulo $2^{16}+1$. If Multiplication Modulo with $2^{16}$ is used instead of $2^{16}+1$ (where $2^{16}$...
-2
votes
1answer
57 views
Security Implications of Multiplication Modulo with a composite
Cryptographic algorithms are designed using an irreducible polynomial. Irreducible polynomial generates entire field and multiplicative inverse of all elements (less zero) exist. A sample ...
0
votes
0answers
40 views
Finding $d$ in RSA Encryption mathematically and by hand
I'm working on this RSA encryption problem and the catch is that it must be done by hand and mathematically.
Let's say $p=11$, $q=13$
$$N=p \cdot q=11 \cdot 13=143$$
I chose $e$ to be relatively ...
3
votes
1answer
27 views
Measure Strength of Mix Mode Modular Arithmetic based Confusion Layer
Strength of sboxes is generally measured by different properties eg non linearity, fixed points etc. If confusion is provided by Mixed Mode Modular Arithmetic (eg as in IDEA), how to measure the ...
1
vote
0answers
136 views
In zkSNARKS, does R1CS require every step of the calculation, or just statements which confirm the calculation was performed correctly?
I was attempting to figure out a way to implement the modulo operation as a set of gates in an Rank-1 Constraint System, detailed by Vitalik Buterin here
However, it occurred to me that maybe we don'...
-1
votes
2answers
85 views
Number theory: efficient modular exponentiation [closed]
If:
\begin{align}
k &= a\cdot b\cdot c\\
k_m &= k \bmod m\\
a_m &= a \bmod m\\
b_m &= b \bmod m\\
c_m &= c \bmod m\\
\end{align}
Then is $B^{k_m} \bmod N$ always equivalent to:
...
-1
votes
1answer
64 views
How to compute this equation $(g^k)^\alpha\bmod p$
I have a question about implementation.
How is an operation like this implemented?
$$(g^k)^\alpha\bmod p$$
With all $g$, $k$, and $\alpha$ being large numbers. The thing that I find tricky is that ...
-1
votes
1answer
39 views
How to understand asymmetric cryptography? [closed]
Everywhere in the lessons on asymmetric encryption explains the process of encryption and messaging, but I'm interested in the asymmetric encryption algorithms themselves. The only thing I have so far ...
1
vote
1answer
120 views
Linear Feedback shift register over integers
The Solina's paper Generalized Mersenne Numbers contains a Linear Feedback shift register I am not able to understand. Here it is:
It is supposed to be a normal Linear Feedback shift register but it ...
0
votes
0answers
30 views
Comparing computational costs of modular multiplication against an elgamal encryption?
I've been looking for a comparison program measure of various encryption schemes relative to individual operations used by the different schemes.
I am having trouble finding one.
What would be the ...
1
vote
1answer
236 views
Coppersmith's method implementation
suppose i have two equations:
$$ (m)^{3} \bmod n = c_{0}$$
$$(m + 2^{k}r + d) \bmod n = c_{1}$$
The values($c_{0}, c_{1}, k, d$) are known.
I wanted to retrieve r (ofc $|r| < n^{\frac{1}{9}})$
...
1
vote
0answers
99 views
RSA high bits padding atack
Can we use Coppersmith's attack if we know a few ciphertexts of the same plaintext, but there is a short random bit padding in front of message? Formula:
$$(2^k \cdot r + m)^3 \bmod n = c$$
0
votes
1answer
53 views
A file chunk in a group/field
I am reading a paper by Shacham and Waters on Compact Proofs of Retrievability. In this paper on page number 3 under section 1.1 in the very first line the author states that an encoded file is broken ...
1
vote
1answer
124 views
How to select elements randomly from a multiplicative group Zn*
I am working on a problem in which I have two large safe primes say p and q randomly selected each of 512 bits. I have generated ...
3
votes
1answer
278 views
Discrete logarithm weak group
I'm looking for weak groups in discrete logarithm, that $x$ can be extracted from $Y$ in polynomial time where $Y \equiv g^x \pmod{p}$ .
I thought one way is to produce a prime $p$ that $p-1$ is an ...
0
votes
0answers
177 views
Is there any benefit to this technique for calculating a multiplicative inverse?
I know very little about cryptography, but many years ago I came up with a relatively simple method for calculating modular multiplicative inverses of binary numbers. My goal was to reduce the ...
1
vote
2answers
236 views
RSA:Plaintext block has a common factor with modulus
I've seen a couple of posts stating the following fact: If $(n = pq,e)$ is the public key of an RSA instance and some plaintext block $m$ has a common factor with $n$, then also the corresponding ...
0
votes
0answers
69 views
MTI/A0: modular arithmetic or elliptic curves?
In the Handbook of Applied Cryptography (Menezes, A. J.; van Oorschot, P. C. & Vanstone, S. A.) Protocol MTI/A0 key agreement (algorithm 12.53) described as $\mod p$-protocol. The survey Overview ...
0
votes
0answers
22 views
EC point addition - Wrong or right answer? [duplicate]
My book says
However, to me the results 11 and 6 doesn't seem right since when i calculate it I get these results:
((7-10)/(9-3)) mod23 = 22.5
and
((3(3^2)+1)/(2*10)) mod23 = 1.4
I am pretty ...
0
votes
1answer
297 views
Decryption using affine cipher
I am doing probabilistic decryption, I was given that A and E had the highest frequency count in the plain text. H and X have the highest frequency in the encrypted text. So in solving for a and b I ...
0
votes
1answer
108 views
SPA resistant RSA trace
I am trying to perform simple power analysis on RSA. In particular focusing the
modular exponentiation module and for this I have implemented left-to-right variant of binary exponentiation.
pseudo ...
8
votes
1answer
208 views
Deterministic RSA blinding
I have an implementation of the RSA private key operation in a context where I don't have access to an entropy source. I'd like to add blinding to it (both message and exponent), to make it resist ...
4
votes
1answer
130 views
Is there a problem using Diffie-Hellman over a Mersenne prime?
Reductions modulo Mersenne primes are extremely fast, and there are several of a suitable size for modp-based Diffie-Hellman (such as $2^{2281}-1$). Is there any reason such primes are not commonly ...
1
vote
2answers
277 views
Does my code have modulo bias
I am writing a password generator in Go, but I want to make sure I am avoiding modulo bias.
My solution is to get a random number from crypto/rand in the range [0, len(alphabet) ** passwordLength),
...
2
votes
1answer
361 views
Is factorization modulo a product of primes an NP-hard problem?
For example, let, $p$ and $q$ be two large prime numbers. We set $n = p \cdot q$.
Now, let $a \cdot b = c \pmod n$.
Given $c$ and $n$, is finding the factors $a$ and $b$ computationally difficult?
I ...
0
votes
1answer
124 views
Confused about final subtraction of modulus in Montgomery Multiplication, during modular exponentiation
I'm confused about how one might supposedly bypass the final subtraction of the modulus in radix-2 montgomery modular multiplication, when used in a modular exponentiation algorithm. The following two ...
