Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [arithmetic]

Arithmetic is a branch of mathematics usually concerned with the four operations (adding, subtracting, multiplication and division) of positive numbers.

1
vote
0answers
53 views

Complexity of arithmetic in (the integer ring of) a number field?

What is the running time complexity (average or worst case) of common arithmetic operations in number fields? In fact, I'm only interested in the integer ring of the quadratic extension $\mathbb{Q}[\...
9
votes
2answers
2k views

How to avoid side channel attacks when handling large numbers?

For cryptography, the platforms have limited size as 32 or 64-bit operations. We definitely need big numbers to implement the encryption/decryption and digital signatures for cryptosystems like RSA, ...
1
vote
1answer
54 views

How to handle points in extended finite field

Following the response to my previous question, I would like to know if you could give me some information or give me a link on how to perform arithmetic operations once I changed a point from the ...
35
votes
3answers
5k views

What is bignum-free RSA?

I recently saw a claim that BearSSL has a bignum-free implementation of RSA. What does this mean? I don't see how one could implement RSA without bignum arithmetic.
4
votes
3answers
236 views

Is there a way of encryption that allows to check what encrypted values are close to their mean?

I am looking for a way to allow parties to publicize encrypted values that can only be decrypted by one or a select few other parties, but that allow everyone to check how close they are to the mean ...
10
votes
2answers
402 views

Why is multiplication uncommon in cryptographic primitives?

Modern computers (which crypto programs are usually run on) have a 64-bit multiply, and it only takes one cycle. It's pretty decent mixing at next to no cost. For block ciphers: Multiplication by ...
6
votes
2answers
466 views

Endomorphism ring of a Elliptic Curve and $j$ invariant

I am reading Schoof's 1995 paper, Counting points on elliptic curves over finite fields, page 236, Proposition 6.1(i). I am trying to understand page 238 (second paragraph) of the proof: if the ...
1
vote
0answers
174 views

How to implement division using Garbled Circuit

Implementing Addition, Subtraction and even N-bit Multiplication can be done fairly quickly and intuitively using garbled circuit, since no looping, control unit nor state machine is needed. One just ...
3
votes
1answer
690 views

Finding sum of two encrypted numbers

Let's consider such process: Two emitents emit two (integer) secret numbers independently They encrypt (encode) these number in such a way that no-one (except emitent) can decode these numbers. ...
1
vote
1answer
192 views

Bilinear pairing arithmetic

Is this $e(g^x,g^yH^z) = e(g^x,g^y)e(g^x,H^z)$ expression is true? where $ g$ is the generator and $ H \in G $
0
votes
1answer
274 views

How to compute accumulated values in bilinear map accumulators

How to compute $ g^{1/(e_1+s)}$, where $g$ is the generator of group $\mathbb G$, and $e_1$ and $s$ are keys? I know only $s$ and $g^{e_1}$, not $e_1$. $\mathbb G$ has prime order for some prime $p$ ...
-1
votes
1answer
82 views

$f : \mathbb{Z}_n \rightarrow \mathbb{Z}^\times_n$?

Is there any function $f : \mathbb{Z}_n \rightarrow \mathbb{Z}^\times_n$ that is invertible? By invertible, I mean it given $y \in \mathbb{Z}^\times_n$, it should be easy to find $x \in \mathbb{Z}_n$ ...
5
votes
1answer
1k views

Purpose of leading zero in PKCS1-v1_5 padding

According to this document the padded message has the following structure: $EM \;= \; 0x00 \; || \; 0x02 \; || \; PS \; || \; 0x00 \; || \; M$ What is the purpose of this null byte at the beginning ...
1
vote
1answer
839 views

ECC Point Multiplication of Product

I can calculate $Q = a\,b\,G$ in several ways: $Q = a \, (b \, G)$ or $Q = b \, (a \, G)$. These give the same result, as expected. But if I do $c = (a \, b) \bmod n$ where $a \, b$ is much greater ...
3
votes
1answer
481 views

Chosen ciphertext insecurity in an ElGamal variant

I'm trying to prove something and if I can show that there is a simple way to calculate $(g^a \bmod p)^k$ if I know both $g^k \bmod p$ and $g^a \bmod p$, then (I think) it will help me prove it, but I'...
1
vote
0answers
308 views

computing inverses in truncated polynomial rings manually for NTRU encryption [duplicate]

Can someone explain how to find inverses in truncated polynomial rings manually (i.e. on pen and paper)? As an example from the tutorial: Example. Take $N=7$, $q=11$, $a=3+2X^2-3X^4+X^6$. The ...
5
votes
2answers
1k views

Timing attack on modular exponentiation

It is known that computing $a^x \bmod N$ takes $O(|x| + \mathrm{pop}(x))$ multiplications modulo $N$, where $|x|$ is the number of bits of $x$ and $\mathrm{pop}(x)$ is the number of $1$ bits (Hamming ...
2
votes
1answer
11k views

Simple example for CP-ABE (Ciphertext policy attribute-based encryption)

I'm currently working on Ciphertext Policy Attribute-Based Encryption (CP-ABE). So far I'm only using it with a basic understanding how it actually works. Now I want to understand it a bit better, but ...
10
votes
5answers
2k views

How to best obtain bit sequences from throwing normal dice?

Throwing normal dice, one can get sequences of digits in [0,5]. In practice, which is the best procedure to transform such sequences into a desired number of bit ...
6
votes
1answer
14k views

What exactly is addition modulo $2^{32}$ in cryptography?

EDIT: I've been confusing this the whole time. What I've been wanting to say this whole time is addition modulo $2^{32}$ not addition modulo 32 as the question originally said. Thanks for pointing ...