# Tagged Questions

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

50 views

### What is proper size of window Using RSA Window method?

I want to Use Window method for RSA modular Exponentiation. because of SCA. But I don`t know what is proper window size.
3k views

### How to find generator $g$ in a cyclic group?

As generator $g$ is used in DH how do you find a combination of prime $p$ and $g$? eg: if we choose $p=23$ and its generator is $7$ (given in the book) how do we find the generator?
63 views

### Given a prime exponent e and a prime number n, find b, where b^e = 1 mod n

Can anyone help me with the following problem. Given a prime exponent $e$ and a prime number $n$, find $b$, where $b^e \equiv 1 \bmod n \land b > 1$. For example, $b^5 \equiv 1 \bmod 11$ how to ...
64 views

### How to decrypt an RSA ciphertext given an oracle providing the lower 8 bits of decryptions?

I have access to an oracle that can encrypt and partially decrypt a number with RSA-1024 algorithm. For encryption: $$C = M^e\bmod n$$ But for decryption, result will ...
68 views

### Compute Modulo exponentiation with prime powers

The problem is to find x such that $$x = M^d \mod p^2$$, where M and d are large numbers, and p is a large prime. Ideally we only want to compute $M^d\mod p$ and then use the result to further ...
37 views

### If A and B are co-primes, does Ax mod B (where x, any positive int) gives {0,1,2,…,B-1}?

If $A$ and $B$ are co-primes (i.e. $\gcd(A,B)=1$), does $A\cdot x \bmod B$ (where $x\in \mathbb N$) give as result an element of $\{0,1,2,....,B-1\}$ ?
126 views

### Why does choosing the first coprime e greater than half of φ(n) result in the same d (private exponent)

While reading on RSA's algorithm, I attempted a simplified implementation and noticed the following: When choosing the public exponent $e$, if the value chosen is the first coprime after $φ(n)/2$ ...
101 views

### How does this affine cipher work?

I have a question about how I need to solve the following: A sentence has been changed to ASCII and then encrypted with the formula $E(x) = ax + b \bmod 256256$. All I know is that the first 4 ...
35 views

### Montgomery multiplication without final subtraction

I am looking for methods to avoid the final subtraction in Montgomery multiplication. I found this paper "A Cryptographic Library for the Motorola DSP56000 " (http://goo.gl/DHePEx) In this paper they ...
67 views

### Scalar Multiplication for Elliptic Curve

Let $\mathbb{E}$ be the elliptic curve $y^2 = x^3 + 6x \text{ mod } 11$ and consider the point $P = (2, 3)$ on it. How do I compute $3P$? I have been able to figure out what $2P$ is, $2P = (5,10)$. ...
59 views

### How to calculate the exponent in modular exponentiation?

I have a problem when calculating power in modular, $a^b \bmod c = d$. where we can know values of $a$, $c$ and d, but we don't know values of $b$. example : $29^b \bmod 1024 = 365$. So, how can I ...
55 views

### Is the one-time pad secure?

I have read about one-time pads (OTP) on Wikipedia. Is this secure? Can I actually use modular addition as ecryption like it said in Wikipedia? And the plaintext is as long as the OTP, so when I send ...
131 views

### How do I create a secure encryption scheme using addition?

You have a 4 number long PIN code with each number ranging from 0 to 9 which you wish to encrypt. You are then given a random 4 digit number ranging from 0 to 9999, which when added to the original ...
63 views

### Multiplying integers modulo $2^{255}-19$ using the Curve25519 polynomial reduction algorithm

I'm reading the Curve25519 paper and I see that in page 11, under the title "Multiplying integers modulo $2^{255}-19$", it says: The coefficients of $x^{10}$; $x^{11}$; ...; $x^{18}$ in $uv$ are ...
95 views

### RSA Encryption problem for Discrete Math

I am doing practice problems for my upcoming final exam, and am having trouble with this RSA encryption problem. If any one could check to see if i did these correctly, it would be greatly appreciated....
44 views

### Binary fast exponentiation method

Evaluate $17^{93} \mod 23$ \begin{align}e &= 93\\ &= 1 × 2^6 + 0 × 2^5 + 1 × 2^4+ 1 × 2^3 + 1 × 2^2 + 0 × 2^1 + 1 × 2^0\\ &= |\ 1011101\ |_2 \end{align} Then we have: \begin{align}17^{...
87 views

### Decrypting an RSA message given $a^2 \equiv 1 \pmod n$

I need help with a practice problem for an upcoming test. I've learned the answer to the problem is "well done", but don't know how to get there. Any help is greatly appreciated. Suppose that the ...
107 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 \leq A,B < N$ in the Montgomery representation ...
There are two number of length m bits. How do I prove that the complexity of modular multiplication of these two numbers is $O(m^2)$.