Vigenere Cipher Methods Is there already a cipher which uses a method like vigenere yet the shifted encrypting alphabets are mixed?

i.e.

ASDFGHJKLZXCVBNMQWERTYUIOP
BNMQWERTYUIOPASDFGHJKLZXCV
CVBNMQWERTYUIOPASDFGHJKLZX

etc.

The Jefferson Disk Cipher is an implementation of this. Each disk is a pre-scrambled alphabet, and the key is the wheel order.


What does a linear function with huge order mean? I am reading this paper "Farfalle: parallel permutation-based cryptography", and there are some terms that I do not understand.

Page 4 says

ratio efficiency vs. safety margin.

What does ratio efficiency and safety margin mean?

Page 5 says

Typically, rollc is a lightweight linear function with huge order,

My question is: What is a linear function with huge order?

Naturally, rolle should have a negligible amount of states in short cycles (preferably none) as they would lead to periodic output sequences

My question is: What does it mean for a permutation to have a negligible amount of states in short cycles?

TL;DR Skip to the bottom for update.
As is well known, the mapping $$L:\{0,1\}^n\rightarrow \{0,1\}^n,$$ of a primitive LFSR on $n$ bits has a single very long cycle of length $2^n-1,$ and a cycle of length $1$ (which maps zero to zero).
As a permutation, this mapping has huge order, i.e., the for almost all the state space the smallest $k,$ such that the $k-$fold composition of $L$ gives the identity map is $k=2^{n}-1:$ $$L^{k}(\cdot)=L(L(\cdots(L(\cdot)))).$$
A randomly chosen permutation on $\{0,1\}^n$ has at least one fixed point with probability $(1-e^{-1})$, and considered as a state mapping, it has a lot of short cycles.
The expected number of fixed points of a random permutation is actually 1, but that is not so relevant, the relevance is the relatively large number of small cycles.
In fact the fraction of permutations with no cycles of length $k$ or less is
$e^{-H_k}$ where $H_k=1+2+\cdots+k$ is the Harmonic number. You can use the approximation $H_k \approx\ln k$ to obtain some rough estimates.
Also see this answer on mathoverflow  for some details. This is not desirable here and the permutation must be carefully chosen.
Edit: For more concrete results see the paper by Odlyzko-Flajolet here where for example, it is proved that the expected "rho length" i.e., initial segment followed by a closed cycle from a random starting point in the state space is $O(\sqrt{N}),$ for a permutation on $N$ points (Theorem 7).
Now compare with the $O(N)$ cycle length in the primitive LFSR example with $N=2^n.$


Homomorphic Encryption, LWE, and Practical Applications I've been reading Brakerski and Vaikuntanathan's Efficient Fully Homomorphic Encryption from (Standard) LWE.

When the authors discuss a small modulus p used for the transition from (n, log q) to (k, log p), how 'small' are they talking about?

If a database has two data types - TEXT (character arrays) and INTEGER (4 or 8 byte integral values), will 'p' ever be 'small' enough to transform an INTEGER value in-situ or in place? Or will the database need a new, larger integer?

I'm asking because I'm curious if an INTEGER value can be encrypted and homomorphically evaluated in a practical sense. I suspect not, but I want to ensure I'm not missing something obvious.

I'll do this backwards

  If a database has two data types - TEXT (character arrays) and INTEGER (4 or 8 byte integral values), will 'p' ever be 'small' enough to transform an INTEGER value in-situ or in place?

No. Homomorphic ciphertexts are still way to big to be stored in a 32 or 64 bit integer. You would likely store the ciphertexts in a string (encoded in some way).

  When the authors discuss a small modulus p used for the transition from (n, log q) to (k, log p), how 'small' are they talking about?

They give the following hint in the paper

  To give a hint as to the magnitude of improvement, we typically set $k$ to be of size the security parameter and $p = poly(k)$. We can then set $n = k^c$ for essentially
  any constant $c$, and $q = 2^{n^\epsilon}$. We will thus be able to homomorphically evaluate functions of degree roughly $D = n^\epsilon = k^{c\cdot\epsilon}$ and we can choose $c$ to be large enough so that this is sufficient to evaluate the ($k$; $\log p$) decryption circuit.

So the size of $p$ is polynomial in the size of the security parameter. Note that the size of $q$ is $n^\epsilon$. $n$ is exponential in the size of the security parameter. So you go from exponential in the security parameter to polynomial, but we are still talking very, very large compared to a 32 or 64 bit integer. I believe ciphertexts in other FHE systems are on the order of kilobytes or megabytes and those were systems that improved upon this scheme.


Why should I use an Initialization Vector (IV) when I have unique keys? I took a look at “Why, or when, to use an Initialization Vector?” but my question is not the same.

I have unique keys encrypting each plaintext (in CBC mode, AES-256) and I do not use a key to encrypt more than one plaintext. Is it insecure to use null IVs in this case? If it is insecure, why?

Caveat: as very rightly pointed in that other answer, using a fixed/no IV does make some attacks less difficult. I wish the following answer would have been less affirmative. I have accordingly made adjustments in italic.

There's no imperious need for an IV when unique keys are used. Given that a 256-bit key cipher is used, what's proposed is safe.

When each key is used only to encipher a single message, it is reasonably safe (from a confidentiality standpoint) to use null IV for all messages. That's customary, for all common modes requiring an IV. It avoids the need to generate an IV, and transmit it, and (in the case of CBC) perform a XOR of the first block with it.

Why? Intuitively: random (or otherwise appropriate) IVs are primarily here to make it unlikely that the same input/output pairs (at the block cipher level, and using the same key) ever occurs during the encryption of two distinct messages, even when one bears some relation to the other (including but far from limited to: starting with the same first block). When there is a single message, that need disappears. More formally, the basic (non-quantitative) proof of security of CBC (and other secure modes) holds without IV when there is a single message per key.

On the other hand, by not using a random IV, in some setups, one gives the adversary the same known plaintext block enciphered with different keys (in CBC, that would be the case if the first block of each plaintext is a known constant); this reduces the number of trial encryptions for exhaustive key search by a factor (at worse) equal to the number $n$ of keys. This is bad, but there are mitigating factors:

The attack only find one of the $n$ keys, and the corresponding plaintext; when theses are independent (e.g. different photos stored enciphered under different keys), the expected number of trial encryptions to revover a certain plaintext is the same as for random IV.
The attack requires searching the result of each trial encryption of the known plaintext among $n$ values. The investment and operating cost for the non-trivial devices that store the ciphertexts blocks and search among them at high rate grows with $n$ (at least the memory capacity is proportional to $n$).

Note: The single message per key setup leaves the total message length per key limit unchanged for CBC, PCBC, CFB: that's $2^{(b+1-k)/2}$ blocks for less than $2^{-k}$ odds of collision (implying some level of insecurity) using a $b$-bit block cipher. That limit is dramatically raised for OFB and CTR in the single message per key setup.


GCM encryption for 256-bit and 512-bit block ciphers The Galois/Counter Mode of Operation (GCM)
This paper describe using GCM mode with 128-bit and 64-bit block cipher. Can we use this mode for 256-bit and 512-bit block cipher?

You could, however the one part that doesn't translate in an obvious manner is the Galois field representation; you would need to pick a field representation for $GF(2^{256})$ and $GF(2^{512})$, because those have not be predefined for those sizes.

Here's the issue; GCM does field multiplications internally; that is, it takes two $N$-bit vectors (where $N$ is the block size of the cipher), interprets them as field elements in $GF(2^N)$, multiplies those two elements, and those maps that result back into an $N$-bit vector.

Why is this a problem?  Well, exactly what is the mapping between bit vectors and field elements?  It turns out that there are a lot of plausible mappings; from a security standpoint, it doesn't matter (the GCM proofs all work regardless of the representation); however it matters a great deal for interoperability.

For the fields $GF(2^{128})$ and $GF(2^{64})$, that's all defined by the standard; in both cases, we use a polynomial representation, using the irreducible polynomial $x^{128}+x^7+x^2+x+1$ for $GF(2^{128})$ and the irreducible polynomial $x^{64}+x^4+x^3+x+1$ for $GF(2^{64})$ (and the bit order is backwards from what you'd expect; so the multiplicative identity (1) is represented by the bit pattern $80$ $00$ $00$ $00$ .. $00$).

All is well and good for the two block sizes specified by NIST, but you are asking about 256 and 512 bit block sizes; even if we stay with a polynomial representation (and the same backwards bit-ordering), you'd still need to select irreducible polynomials of the correct degree.

Looking through the web, I see a claim that the polynomials $x^{256}+x^{10}+x^5+x^2+1$ and $x^{512}+x^8+x^5+x^2+1$ are irreducible; I cannot confirm that (and the web site has a cavaet as well); however if so, they would be viable options.  This paper also lists some primitive (and hence irreducible) polynomials, however they aren't minimal (which would be the obvious one to use)


About DDH over cyclic group Z*p^2 To construct a secure multiparty computation function, we need to use the cyclic group G = Z*p^2 with p is a large prime. However, we are uncertain that DDH holds over this group.

Can you show that DDH holds/doesn't hold over the cyclic group Z*p^2?

Note that: the order of G is q = p(p-1) and q is multiple of the large prime p.

Thank you very much!

I would say that DDH does not hold in $Z^*_{p^2}$.

Let's first consider DDH in $Z^*_{p}$. We know DDH is not hard because given a DDH tuple $(g^a,g^b,g^c)$, one can compute the Legendre symbols $(L(g^a),L(g^b),L(g^c))$, and know whether they are quadratic residues or not. If any of $(g^a,g^b)$ is a residue but $g^c$ is not, then we know $c\ne ab$.

It has also shown by Gauss that a number co-prime to an odd prime $p$ is a residue modulo any power of $p$ if and only if it is a residue modulo $p$. Thus the above can be extended to $Z^*_{p^2}$.


At the current time, is SHA256 the de facto standard for strong cryptographic hashes? At the current time, is SHA256 the de facto standard for strong cryptographic hashes?

From what I am seeing of more sites utilizing it, I would suppose the answer to this is yes, but would like to hear what the community here has to say about this and why it is happening.

Yes, SHA-256 is currently the de facto standard. The "why" is that MD5 and SHA-1 are unsafe and the only algorithm left which has been extensively studied and deployed and which nobody has found a significant attack against is SHA-256. (There is also SHA-512, but people seem to regard it as being overkill.)

There is widespread uncertainty about whether someone will discover an efficient attack on SHA-256 in the near future. It was this fear which motivated the SHA-3 competition.

You should also consider using a generic length-extension defense such as the "SHA-256d" design by Ferguson and Schneier. SHA256d(x) = SHA256(SHA256(x)). If you don't use a generic length-extension defense then you have to consider the consequences of length-extension attacks in each place that you use a hash function. Such considerations can be tricky, and if you misunderstand one, this can sometimes cause a security vulnerability. This is why it is safer to use a generic length-extension defense every time you use a hash function.

If for some reason you don't want to use SHA-256, and you don't want to use a new hash function such as a SHA-3 candidate, then you might also consider Tiger. It has the distinction of being one of the longest-serving hash functions for which there is no known practical attack. However, it has been seriously wounded (i.e. by impractical but theoretically significant attacks), and I would consider SHA-256 safer than Tiger at this point. If efficiency matters, Tiger is faster than SHA-256, SHA-1, or any SHA-3 finalist on 64-bit hardware. It doesn't come with generic length-extension defense built in, but you can of course define Tigerd(x) = Tiger(Tiger(x)).

I would also regard the current crop of SHA-3 finalists as very likely to be secure: http://ehash.iaik.tugraz.at/wiki/The_SHA-3_Zoo . They are much newer, of course, than SHA-256, but they were all designed with a thorough understanding of the flaws in MD5 and in SHA-1, and they have been subjected to intensive scrutiny for almost three years now. They all come with generic length-extension defenses. My favorites are Blake and Skein, which are faster than SHA-256 on Intel/AMD chips. Unfortunately all of the SHA-3 candidates are slower than SHA-256 on ARM chips.

Don't use MD5 or SHA-1. Please.


Question about OpenSSL testing for FIPS 186-4 and using BN_generate_prime_ex I am working on testing my implementation of OpenSSL using the CAVP
186-4 RSA Validation System (RSA2VS).

There are tools under openssl-fips-2.0.16/test and I am working on modifying fips_rsagtest.c to process the 186-4 test vectors the way I need them.

The fips_rsagtest.c program was originally made to take in values for Xp1, Xp2, Xp, Xq1, Xq2, and Xq from an input file and generate the primes p and q.

But the newer tests require I generate the random values Xp1, Xp2, Xp, Xq1, Xq2, and Xq on my own.  Looking at fips_rsagtest.c, it would create the primes p and q using the function RSA_X931_derive_ex().

I looked through these X931 functions and they do not appear to be the same functions OpenSSH calls: RSA_generate_key_ex().

My test lab has informed me that they have validated OpenSSL against 186-4 so I'm wondering if those implementations had custom code in them or if the built-in functionality in the current OpenSSL was able to pass the CAVP 186-4 tests.

That leads me to my 2 questions:

Q1) Does anyone know if it is OK to use these X931 functions for 186-4 testing?

Q2) If they are not, any pointers on how can I get these Xp1, Xp2, Xp, Xq1, Xq2, and Xq values out of the regular RSA_generate_key_ex() function?  It appears to use BN_generate_prime_ex() but there are no obvious variables with the Xp1, Xp2, Xp, Xq1, Xq2, and Xq labels.

Thanks for any insight you can provide!

I believe I have answered my own question.  It appears that OpenSSL uses FIPS 186-4 Appendix B.3.3 to produce its primes instead of Appendix B.3.6.  The FIPS algorithms were using Appendix B.3.6 which is why I was out in left field.

Appendix B.3.3 does not use the Xp1, Xp2, Xp, Xq1, Xq2, and Xq values to produce the primes p and q.

I've started writing a test tool from scratch that isn't linked to the FIPS code instead of updating fips_rsagtest.c which just didn't want to work anyways (had issues getting the RBG to work in it).


Elliptic curve and "vanity" public keys I want to find an algorithm to get a private/public key pair where one coordinate of the public key has some specific prefix (for example: 20 leading zeroes).
In the secp256k1 case (the Bitcoin curve), G. Maxwell has found a public key with coordinate

x = 00000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63

( see https://bitcointalk.org/index.php?topic=90982.msg13789635#msg13789635).
In that case 22 zeroes means 88 bits, and he claimed to have found the private key too. Obviously $2^{88}$ random tries are computationally infeasible, then I think that the Birthday Paradox should be used (to reduce the steps from $2^{88}$ to $2^{44}$). But I can't understand how to apply the Pollard Rho algorithm (the classic Birthday Paradox - based algorithm) to this specific task.  Any ideas?
EDIT1:
It is very simple to find only a public key with as many leading zeros as you want without the private key, for example:

x = 0000000000000000000000000000000000000000000000000000000000000001
y = 4218f20ae6c646b363db68605822fb14264ca8d2587fdd6fbc750d587e76a7ee

are the coordinates of a valid point of the secp256k1 curve because they fulfill the equation $y^2 = x^3 + 7$ mod $p$
That's why I'm pretty sure that G.Maxwell has the private key too (otherwise his public key would have nothing special)
For now I know that if I generated about $2^{44}$ random points, I would find a "partial" collision, i.e. I would find a couple of points $P_1$, $P_2$ with $x_{P_1}$ and $x_{P_2}$ that share the first 88 bits. How do I use this information to find a point $P_3$ with 88 leading zero bits?
EDIT2:
Very strange: it seems that it takes $2^{88}$ steps to find a private key to any public key with a specific 88 bit prefix,
but it takes only $2^{128}$ steps to find a private key to a single specific public key (with a specific 256 bit "prefix") using the Pollard Rho algorithm  (see http://andrea.corbellini.name/2015/06/08/elliptic-curve-cryptography-breaking-security-and-a-comparison-with-rsa/ or https://blog.coinfabrik.com/wp-content/uploads/2016/06/ECDSA-Security-in-Bitcoin-and-Ethereum-a-Research-Survey.pdf)
Then to find a private key to any public key with a specific m bit prefix, with $m> n/2$, Pollard Rho is the best shot, with $m\leq n/2$ the fgrieu method is the best.

Maxwell's vanity public key is a result of how the generator of the secp256k1 was chosen; as explained by Maxwell himself.

For some reason, the generator $G$ is the double of the point:

x = 0x00000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63,
y = 0xc0c686408d517dfd67c2367651380d00d126e4229631fd03f8ff35eef1a61e3c

which is exactly Maxwell's vanity public key. Its private key is 0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a1 which is $1/2$, i.e. the inverse of $2$ modulo the curve order $n$. This is also equal to $(n+1)/2$.

The big question is: why was the secp256k1 generator chosen like that? I have no idea. But note that it's not difficult to find a generator with a lot of leading zeroes.


Side channel attack - execution time depends on the size of the key In my algorith execution time depends on the size of the key. It is a linear relationship (probably). The larger the key, the longer the algorithm takes to run. I have a code in Python so far.
For example for 3-bit round keys it runs 1 sec and for 128-bit round keys it runs 4 sec (for some number of inputs).
Is this a disqualifying problem?
PS By the way I will precise why it happens. There are simply additions and multiplications. It takes more time to multiply plaintext by bigger number, the same is with adding. What's more there are some equations to solve with euclidean algorithm, where we got for example to solve $2^{128} \cdot c - key^{64} \cdot k = 1$. I don't how $key$ size can affect time of solving that.

Execution time of my algorithm/code depends on the size of the key. Is this a disqualifying problem?

No, because the key size is not considered a secret.
But having execution time depend on the bit size of the integer coded by the key would be something different. It would be a problem, more or less minor depending on the size we are talking about and algorithm/key generation method. For example, in RSA, that's typically not a serious issue for any of the integers defining the private key $p$, $q$, $d$, $d_p$, $d_q$, $q_\text{inv}$, because it's so unlikely that the bit size of these integers is significantly reduced compared to its maximum; and regarding $p$ and $q$, their bit size as an integer is customarily fixed to exactly half the bit size of $n=p\,q$.
What could be a serious side-channel issue would be that execution time depends on some secret data, like the key value, or plaintext in an encryption algorithm. The worse is when execution time depends on a combination of the key value and varying information known or under control of adversaries (e.g. key and ciphertext; or key and hash of signed data). That's ideal ground for a side-channel attack. That could well be the case if multiplication time depends on the value multiplied. That's a common and hard-to-avoid issue, see this.


El-Gamal signature with two messages Alice uses an ElGamal signature with base the group $Z^*_{107}$ and parameter $g=3$ of order $q=53$.The private key of Alice is some $x \in \{0,1,.....,52\}$ and the public key of her is $y=10$. To sign the message m, she calculates $r=g^k \bmod107$ for $k \in \{0,1,......,52\}$ and $s=(k \cdot h(m)+r\cdot x) \bmod 53$. For signing the first message, Alice chooses a random $k_1 \in \{0,1,......,52\}$. To sign  the second message she uses $k_2=(2 \cdot k_1 +1) \bmod 53$ and generally if for the signature of $i$-th message she has used the $k_i$ for the $(i+1)$-th message she uses the $k_{i+1}=(2\cdot k_i +1)\bmod 53$. You know two successive signatures of Alice: $(r,s)=(79,7)$ of message $m$ with $h(m)=2$ and the signature $(r',s')=(105,41)$ of message $m'$ with $h(m')=3$. Find the private key of Alice (of course withουt calculating directly any discrete logarithm in group $Z^*_{107}$)

I am trying to solve this. I tried to apply the ElGamal Algorithm but I do not know how to use the $h(m)$ hash function. Can anyone help to solve it and help me how to use correct the ElGamal signature?
(source: mathematical competition 2008,France)

Before continuing to read this answer, read my above hint:

  Try writing down all the equations for the different s and try to solve the system of equations.

If you still can't solve this one, you may read the remainder of the answer.

First observe that $s_1 \equiv k_1 \cdot h(m) + r_1\cdot x \pmod {53}$ and $s_2 \equiv k_2 \cdot h(m') + r_2\cdot x \pmod {53}$ where only $k_1,k_2,x$ are unknown. So 3 variables for 2 equations, which isn't solvable, right?
Here's where the special relation comes into play. Replace $k_2$ by $2k_1+1$ which yields

$s_2\equiv (2k_1 + 1) \cdot h(m') + r_2\cdot x\equiv 2k_1\cdot h(m') + h(m') + r_2\cdot x \pmod {53}$

Now subtract the first equation twice times $h(m')$ from the second equation times $h(m)$ which yields:

$s_2\cdot h(m) - 2\cdot h(m')\cdot s_1 \equiv h(m)\cdot h(m')+r_2 \cdot h(m)\cdot x - 2r_1 \cdot h(m') \cdot x \equiv h(m)\cdot h(m')+ x \cdot (r_2\cdot h(m) - 2r_1\cdot h(m')) \pmod {53}$

Finally multiply by the inverse of $r_2\cdot h(m) - 2r_1\cdot h(m')$ ($=(r_2\cdot h(m) - 2r_1\cdot h(m'))^{-1}\bmod 53$) and subtract $h(m)\cdot h(m')$. This gives us the following equation for retrieving $x$:

$x = (s_2\cdot h(m) - 2\cdot h(m')\cdot s_1)\cdot (r_2\cdot h(m) - 2r_1\cdot h(m'))^{-1} - h(m)\cdot h(m') \bmod 53$


Proof that $gcd(e, \lambda(N)) = 1 \hspace{1mm} \Longleftrightarrow \hspace{1mm} gcd(e, \varphi(N)) = 1$ What is the proof for the fact that
$gcd(e, \lambda(N)) = 1 \hspace{1mm} \Longleftrightarrow \hspace{1mm} gcd(e, \varphi(N)) = 1$

Where:

$N = P * Q$ where $P$ and $Q$ are both primes.

$\varphi(N)$ is Euler phi function

$\lambda(N)$ is Carmichael function

An outline of the proof is:

$gcd(a,b)=1$ is equivalent to the claim that $\not\exists p_\text{ prime}: p|a \land p|b$ (that is, there does not exist a prime $p$ that is a factor of both $a$ and $b$)

Now, for all primes $p$, $p | \phi(N)$ iff $p | \lambda(N)$ (that is, for all primes $p$, either they are a factor of both $\phi(N)$ and $\lambda(N)$, or they are a factor of neither).  This can be seen by examing the relation $\phi(N) = (p-1)(q-1)$ and $\lambda(N) = (p-1)(q-1)/gcd(p-1,q-1)$, and observing that if $gcd(p-1,q-1)$ had a prime power factor $r^n$, then both $p-1$ and $q-1$ were multiples of $r^n$, and hence $(p-1)(q-1)$ had $r^{2n}$ as a factor, and so $(p-1)(q-1)/gcd(p-1,q-1)$ has $r^n$ (and hence $r$) as a factor.

So, if $gcd(e, \lambda(N))=1$, then:

For any prime factor $p$ of $e$, $p$ is not a factor of $\lambda(N)$
Hence, For any prime factor $p$ of $e$, $p$ is not a factor of $\phi(N)$
Hence, $gcd(e, \phi(N))=1$

And versa-visa, showing the equivalence.


How does this POLYVAL modular reduction algorithm work? I recently found the GitHub repository used to make the measurements in the AES-GCM-SIV paper where they implement polynomial hashing using POLYVAL.

This means in this context to compute the usual $\tau=\sum_{i=0}^nm_iH^{n-i}$ for 16-byte message blocks $m_i$ and a 128-bit key $H$ in the usual way as $H_{i+1}=(m_i+H_i)\cdot H$ with messages and $H$ being interpreted as polynomials over $\mathbb F_2[x]/(x^{128}+x^{127}+x^{126}+x^{121}+1)$.

Now the actual computation uses x86 hardware intrinsics (which can be looked up here).
The code in question is Polyval_Horner (polyval.c, line 137) in particular the following extract (adopted and commented from the repo):

__m128i TMP0, TMP1, TMP2, TMP3, TMP4, T, POLY, H;
H = _mm_loadu_si128(((__m128i*)pH));
T = _mm_loadu_si128(((__m128i*)TAG));
// ordering of the inputs is reversed, last is most significant
// 0xc2000000 corresponds to the top 3 POLYVAL coefficients
POLY = _mm_setr_epi32(0x1,0,0,0xc2000000);

T = _mm_xor_si128(T, _mm_loadu_si128((__m128i*)inp));
// This instruction takes two 64-bit halves and carrylessly multiplies them
// If the lower nibble is 0, take the lower half of the first input, else the upper half
// likewise with the upper nibble for the second input
TMP1 = _mm_clmulepi64_si128(T, H, 0x00);
TMP4 = _mm_clmulepi64_si128(T, H, 0x11);
TMP2 = _mm_clmulepi64_si128(T, H, 0x10);
TMP3 = _mm_clmulepi64_si128(T, H, 0x01);
// TMP2 and 3 contain the range of coefficients from 64 to 191, add them
TMP2 = _mm_xor_si128(TMP2, TMP3);
// now extract the upper and lower halves of these coefficients and add them
// into either TMP1 or 4 depending on whether they are the lower or the upper coefficients
TMP3 = _mm_slli_si128(TMP2, 8);
TMP2 = _mm_srli_si128(TMP2, 8);
TMP1 = _mm_xor_si128(TMP3, TMP1);
TMP4 = _mm_xor_si128(TMP4, TMP2);
// reduction starts here
// multiply the lower half of TMP1 with the upper half of POLY
TMP2 = _mm_clmulepi64_si128(TMP1, POLY, 0x10);
// This re-orders the 32-bit subwords
// 78 should exactly swap the 64-bit halves
TMP3 = _mm_shuffle_epi32(TMP1, 78);
TMP1 = _mm_xor_si128(TMP3, TMP2);
TMP2 = _mm_clmulepi64_si128(TMP1, POLY, 0x10);
TMP3 = _mm_shuffle_epi32(TMP1, 78);
TMP1 = _mm_xor_si128(TMP3, TMP2);
T = _mm_xor_si128(TMP4, TMP1);

(I have not converted to pseudo-code as to preserve any specific instruction behavior I may get wrong).
This code loads a key pH and a previous iteration TAG adds it with some 16-byte input inpand multiplies it with pH in a carryless way and then reduces it modulo the Polyval polynomial into the new value of T.

My reading of the above code is that

Before the reduction TMP4 holds the 128 most-significant polynomial coefficients of the multiplication result
Before the reduction TMP1 holds the 128 least-significant polynomial coefficient of the multiplication result

Now my question is:

How does this reduction algorithm work?

Because for me, if I try it on paper with $x^{127}$ and $x$ I should get back $x^{127}+x^{126}+x^{121}+1$ but instead I think the algorithm returns me $1$.

Here's my interpretation of how to read the reduction intrinsics:

Take the lower 64-bit of the lower 128-bit of the multiplication result, multiply them with the upper 64-bit of the polynomial (in my example that's $0$ times the upper bits), call it TMP2
Swap the 64-bit halves of the original 128-bit result, call it TMP3 ($0$ in my example because TMP1 would be 0)
Add TMP2 and TMP3, call the result TMP1 ($0+0$)
Repeat the previous three steps once
Return the addition of the current TMP1 and TMP4 (the upper 128-bit) which in my case would be $0+1=1$

From the paper if you look at section 2.3 you will find an explanation of the reduction. The reduction from a code execution prospective works by reducing the number of operations of GHASH.
From a theoretical stand point the paper authors took an incorrect derivation direction of the first induction proof. However their mistake resulted in discovering a differential set linkage between POLYVAL and GHASH.
Where A ^ B --->  D0  and Z* is the number of checks to determine the value of D0. After completing running GHASH the function returns D*. From this the operator can say B ---> D0 and Z < Z*.


Is there any IND-CPA secure stream cipher with a "standard" hardness assumption? I've read our recent question: "One-time pad using RSA and Diffie-Hellman functions" which asks about the security of a particular way to convert RSA and discrete exponentiation into a stream cipher. The approach didn't work out, as expected, knowing that it was an interview question.

Now, the following question came over me:
Is it (constructively) possible to create a stream cipher whose IND-CPA security can be directly reduced to a well-known number-theoretic assumption?

To be clear: I'd like to know (out of curiosity, no deployment intended) whether there exists a stream cipher which is as hard to break as CDH (or another assumption) with no other assumptions (no random oracles, no constructed PRPs like AES, no constructed PRFs like SHA-2, ...) and if such a stream cipher can exist , I'd also like to know how to build it (e.g. give a brief description please).

Example assumptions: "factoring is hard", "the RSA problem is hard", DLOG, CDH, DDH

Sure.

one-way permutation  +  strong hard-core functions
$\to$
pseudorandom generator
$\to$
stream cipher

The keystream is concatenation of the strong hard-core function's values at

the iterates of the one-way permutation on the key.  ( k,f(k),f(f(k)),f(f(f(k))),... )


Key derivation after ECDH: why h(q ‖ pk1 ‖ pk2)? I want to use the X25519 DH key agreement for generating a single AES-128 key.
The distribution of the shared secret of such a key agreement is not uniform, so it shouldn't be used directly.

The libsodium docu suggests to hash it with: h(q ‖ pk1 ‖ pk2).
As hash function h() I want to use SHA-256. As the output is 256 Bit I would just use the lower half.

Why do you append the public keys there? Shouldn't h(q) be good enough?

I'm not sure whether it's the only reason, but adding pk1 and pk2 gives you more entropy, hence a higher security level. Like the docs say, the number of points on the curve is $\approx 2^{252}$, so for a 256-bit hash function $h$ you have $\#\{ h(q) \}_q = 2^{252}$ instead of $2^{256}$.


Can you help me with this DES variant analysis? I'm struggling with some DES variant that I got as an exercise (exercise taken from Katz-Lindell Ex5.14).

The variant is as follows:

The left half of the master key is used to derive all the sub-keys in rounds 1-8, while the right half of the master key is used to derive all the sub-keys in rounds 9-16.

My direction is to execute a meet-in-the-middle attack. We can observe that if we guess the 28 bit left-half of the master key we can completely compute $L_8$ and $R_8$, also, if we guess the 28 bit right-half of the master key we can completely compute $L_8$ and $R_8$ too, but now by the inverse direction. So we extensively guess all the possible keys for the right-half and for the left half which will take $O(2\cdot2^{28})$ time and space - since for each guess $L_k$ of left-half key we store $L_k:<L_8,R_8>$ computed by it and we store all those key-value pair in the set $S_L$, we do the same for the right-half guesses and store the values in set $S_R$. Of course the correct $L_k$ and $R_k$ will apply the same $<L_8,R_8>$.

My question

How many $L_k$ and $R_k$ would I find? How to analyse this?
How many plaintexts & ciphertexts pairs would I need to find the key with high probability? How to analyze this?

Each half of the key is 28 bits long, so there will be $2^{28}$ possible choices for each of them.

In the first part of your attack, you start with the known block of plaintext and encrypt it for the first 8 rounds using each possible left half of the key.  This gives you $2^{28}$ "half-encrypted" 64-bit blocks.  This is less than the birthday bound, so most likely the blocks will all be distinct, although there's a small chance (about 1 in $2^9$) of there being at least one collision.  Still, for practical purposes, we can assume the number of distinct half-encrypted blocks to be close to $2^{28}$.

In the second part of your attack, you start with the known block of ciphertext, decrypt it for 8 rounds using each possible right half of the key, and look the resulting "half-decrypted" block up in the list of half-encrypted blocks compiled in the first part of the attack.  Obviously, if the ciphertext is indeed the result of encrypting the corresponding plaintext with the modified DES algorithm you describe, there will be at least one match corresponding to the correct pair of half-keys.

As for the other half-keys, each of the $2^{28}$ right halves has a $2^{28}/2^{64} = 1/2^{36}$ chance of producing a half-decrypted block that, just by chance, matches one of the half-encrypted blocks computed in the first part.  Since these probabilities are essentially independent, the total expected number of "false positive" matches is $2^{28} \times 1/2^{36} = 1/2^8$.  By the law of rare events, the actual number of false positives is approximately Poisson-distributed, and, since the expected number is significantly less than one, the probability of there being at least one false positive is also approximately equal to the expected number.

Thus, with probability about $1 - 1/2^8$, just carrying out this meet-in-the-middle attack on one pair of known plaintext and ciphertext blocks will yield a single pair of half-keys corresponding to the correct key.  If you do get unlucky and end up with multiple candidate keys, testing them on a second plaintext / ciphertext block will rule out each of the false ones with probability $1 - 1/2^{64}$.

Edit: (Copied and extended from comments below.) All of the analysis above is in the ideal cipher model, i.e. it assumes that each of the halves of your modified DES can be treated as if it were a family of random permutations (of the set of 64-bit blocks) indexed by the corresponding 28-bit half-key. Of course, neither DES nor your modified version of it are actually ideal ciphers, but, like any good block cipher, they're designed to generally look like one, so for basic statistical analysis like this, the ideal cipher approximation is usually good.

If the statistical behavior of your (half-)DES variant turned out to be significantly different from an ideal cipher when the attack was actually carried out, this would most likely imply a much more fundamental weakness in the cipher than the mere(!) vulnerability to meet-in-the-middle attacks (not that it isn't a devastating vulnerability in itself, given the already low key length). In particular, note that several of the various known deviations of DES from an ideal cipher, such as the complementation property, don't really apply here since we've fixed the input.

As for the $1/2^9$ collision rate, $2^{28}$ keys give $2^{28}(2^{28}-1)/2 \approx (2^{28})^2/2 = 2^{55}$ pairs of outputs. Each of these outputs has approximately a $1/2^{64}$ chance of colliding (assuming independence, which is of course not really true, but a reasonable approximation), giving an expected number of $2^{55}/2^{64} = 1/2^9$ collisions. Since this is much less than 1, by the law of rare events it also approximately equals the probability of there being at least one collision.

Another way of calculating the collision probability is to note that, in order to get no collisions among the $2^{28}$ half-encrypted blocks, each of them must evaluate to a distinct 64-bit value as we calculate them one by one.  Thus, the exact probability of not getting a collision (under the ideal cipher assumption) is

$$\begin{aligned}
& (1 - 0/2^{64})\cdot(1 - 1/2^{64})\cdot(1 - 2/2^{64})\dotsb(1 - (2^{28}-1)/2^{64}) \\
\approx& 1 - 0/2^{64} - 1/2^{64} - 2/2^{64} - \dots - (2^{28}-1)/2^{64} \\
=& 1 - (0 + 1 + 2 + \dots + (2^{28}-1)) / 2^{64}  \\
=& 1 - (2^{28}(2^{28}-1) / 2) / 2^{64} \\
=& 1 - 1/2^9 + 1/2^{37} \\
\approx& 1 - 1/2^9
\end{aligned}$$


In HMQV, can one use multiple identities with one public key? The HMQV protocol has 2 "identity" fields $\hat{A}, \hat{B}$ that are used in the dual signature - and it tries to guarantee that any properly-generated session key is only shared by a single $(A, B, \hat{A}, \hat{B})$ 4-tuple.

However, the paper isn't particularly clear whether a party can use multiple, potentially attacker-controlled, identities.

I think you are not familiar with the PKI-based setting. In the PKI-based setting, each user owns a certificate that binds his/her identity with his/her public key. If a user uses multiple identities with one public key, that means he/she must use same public key with a different identity to register many times, at this point he/she will receive different certificates(the number of which is the number of the identities belonging to a user). Well, this is very easy to avoid in the CA, it is only required that repeated registering is not allowed.

Actually, even if this case happens, then HMQV is still secure only if the secret key corresponding to the same public key isn't compromised.


Does it matter if I append the secret to the salt or pass it in separately? I'm using PBKDF2, and this is my current call.

key = pbkdf2-hmac-sha256(iterations = 100_000, secret = password ++ salt)

I recently learnt that the function I'm calling also takes an optional salt field, and passing the salt instead of appending it gives different answers. Is what I'm currently doing insecure? I don't think it is, but I want to be safe - it looks like PBKDF2 uses the secret many times, but the salt only once, and there might be a good reason for that.

What you have been doing is unconventional, but is cryptographically safe, and should be fine as long as the implementation of pbkdf2-hmac-sha256 is correct. Things to watch out:

is all the stuff (characters?) in password and salt safely kept by whatever ++ is?
is this secret then converted to octets without entropy loss on entry of pbkdf2-hmac-sha256 ? Changing anything non-ASCII to ? is a goof that has crept; combined with use of a foreign language, overly paranoid user, or an endianness problem, that could degenerate to the length of the secret being the only entropy left! Another issue that can creep is stopping at the first zero octet in secret.
Does the pbkdf2-hmac-sha256 implementation correctly handle the case when secret, converted to octets, exceeds 64 octets? The action pbkdf2-hmac-sha256 should perform in this case is to replace these octets with their 32-octet SHA-256 hash.

Given this, the worst I can think the unconventional use of pbkdf2-hmac-sha256could cause is that timing execution could leak the length of password in an easier manner, but that's a non-issue.

Before that comment, I knew no language where 100_000 is a valid constant. More importantly, a hundred thousands is an insufficient iteration count nowadays for PBKDF2-HMAC-SHA-256, a short memorable password, and protecting a key from exhaustive search. Modern password-based key derivation functions make use of memory, sometime multiple execution threads, to greatly increase their effectiveness at a given execution time or cost, e.g. scrypt, Argon2, Balloon.

Note: implementing the core of PBKDF2-HMAC-SHA-256 in something that ultimately is interpreted rather than somewhat compiled would be a huge (but not rare) design mistake, since it would force using a lower iteration count than would be otherwise possible.


Equivalent RSA modulus for NIST P-192 and P-521 elliptic curves At www.keylength.com, I found the following table of ECC field size and the corresponding RSA modulus recommended by NIST.

ECC Modulus  RSA Prime Size

160             1024

224             2048

256             3072

384             7680

512             15360

But NIST proposed P-192, P-224, P-256, P-384, P-521 curves. May I know what is equivalent RSA modulus for P-192 and P-521 curves?

Security strength of RSA in relation with the modulus size outlines the formula that is used for the strength of an RSA key (as a function of the size of the modulus).

For ECC it's a simpler "the prime field size / 2".

So ECC-192 => 96 bits of security.  $\sqrt[0.43]{96 / 4}$ = $\sqrt[0.43]{24}$ = $1621$, with $1624$ being the next highest number divisible by 8.

ECC-521 => 260.5 bits of security.  $\sqrt[0.43]{260.5 / 4}$ = $\sqrt[0.43]{65.125}$ = $16520.3$, making $16528$ the equivalent, which is beyond most systems' maximum of 16384.


What Feistel network block ciphers do not use data-dependent table lookups or modular additions? I am looking for block cipher algorithms based on Feistel networks. The algorithm is required to not use data-dependent table lookups (or data-dependent rotations) or modular additions/multiplications.

The only two algorithms that I have found are Simon and Simeck. Are there any alternatives?

I didn't wish to post an answer because I don't want invent any scheme that may cause security hole in somebody elses' system. But here I'll do a bit of illustration for you.

Because both Gimli and Keccak have large enough block size in their typical instantiation, we can simply put key in one half and cipher block data in another half (zero-extend if needed repeat key bytes if needed, as is being done with ChaCha20 and Salsa ciphers):

Gimli: [ data 128 bits | key 128,192,256 bits ] 384 bits.

Invoke the permutation:

Gimli: [ Random....... | Bitstring........... ] 384 bits.

And bring it into the Feistal network:

[ Block half A | Block half B ] // Plaintext block.
       |              |
       |      Key     V
   data:->[Permute]->[+]
       |              |
       V              V
[ Block half A | Block half B']
       |              |
       V      Key'    |
      [+]<-[Permute]<-:data
       |              |
       V              V
[ Block half A'| Block half B'] // Ciphertext block.

Possible ways to increase security:

Increase the number of rounds from 2 to higher,
Derive a key schedule for example by running the permutation in XOF sponge mode.


Inverse in ElGamal signature I am learning about ElGamal signature verification. During the signature generation one has to choose a k such that 1 < k < p − 1 and gcd(k, p − 1) = 1. I am using the notation from the Wikipedia site. Later it is used the inverse of k. I assume this is a modular inverse. Learning materials I have found does not state whether this is a modular inverse regarding p or p-1. Can somebody clarify this?

In ElGamal Signature Scheme we have:

$$\beta=\alpha^a \bmod p$$

The values $p,\alpha$ and $\beta$ are public key, and $a$ is private key.

$$\operatorname{sig_k}(x,k)=(\gamma , \delta)$$

  where $\gamma = \alpha^k \bmod p $ and $\delta = (x-a\gamma)k^{-1} \bmod {p-1}$.


Fully understanding bitcoin transcation verifying and secp256k1 Hello fellow cryptographers.
I have spent last few days trying to understand and find a way to generate secp256k1 private and public keys from scratch, but i failed.
I have seen tons of videos and read tons of pdfs about it but I still can't understand how to implement it even in pseudocode.
r = Random
k = PrivateKey (64bit hex string that should safely be generated from r and hashed)
K = PublicKey
G =
0479BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798483ADA7726A3C4655DA4FBF0E1108A8FD17B448A68554199C47D08FFB10D4B8

K = k * G

Now i know G has x,y and that 04 at the beginning means that its in uncompressed form.
But i am confused with the way I should multiply k and G, since whenever I tried turning them into decimal values multiplying them and then encoding them into hex afterwards I would get wrong results.
Now lets say I have K(public key).
How would I go about encrypting an message, and then proving that I can decrypt it?
I really look forward to hearing your answers :D

G is a point on the curve, but multiplication on elliptic curves is not the same as just multiplying the x and y value by the number.
Have a look here https://en.m.wikipedia.org/wiki/Elliptic_curve_point_multiplication to see how you multiply a Point (G) with a natural number.
Because the elliptic curve, you are talking about, is not over the real numbers, but over a residual field (natural numbers mod N), the division is just another way to write the multiplication by the inverse (mod N) https://en.m.wikipedia.org/wiki/Modular_multiplicative_inverse


Collision-resistant Pseudorandom function Assume we have a pseudorandom function: PRF(.)

We want the following property holds with a high probability:

$\forall i, 0\leq i \leq n: PRF(k_1, i)\neq PRF(k_2,i)$

where $k_1$ and $k_2$ are two random keys picked independently.

Question 1: What is the pseudorandom function with the above property called in the literature?

Question 2: Is there any paper using the above pseudorandom function?

The question seems that it could be implying that you actually intended to ask about probability of any given index not colliding, as opposed to the probability of every index simultaneously not colliding. If this is the case, then the answer is trivial: Two outputs of any PRF, even at the same index, are independent random variables by definition and therefore collide with probability $\frac{1}{n}$.

However, in the case that you really do mean the universal notion, the situation is just slightly more involved: Any PRF with an output size $a$ (in bits) and an input size $b$ has this property with probability approximately $1-2^{a-b}$.

To see this, let $\rho$ denote the probability that the desired property holds, and take the codomain to be of size $\alpha n$ where $\alpha$ is a constant.

$$\rho = \Pr(\forall i \in [0, n]: PRF(k_1, i)\neq PRF(k_2,i))$$
Assuming the values are i.i.d:
$$\rho = \Pr(PRF(k_1,i) \neq PRF(k_2,i))^{n+1}$$
Assuming the values are uniform:
$$\rho = \left(1-\frac{1}{\alpha n}\right)^{n+1}$$
Taking the limit as $n\to\infty$:
$$\rho \approx e^{-1/\alpha}$$
Which is within 5% of the true value when $n \geq 32$ and $\alpha \geq 1$. We assume $\rho = 1-\frac{1}{z}$ and solve for $\log_2\alpha$, which is by definition the number of output bits minus the number of input bits:
$$e^{-1/\alpha} = 1-\frac{1}{z}$$
$$\alpha = \left(\log\frac{z}{z-1}\right)^{-1}$$
$$\log_2\alpha = -\log_2\log\frac{z}{z-1}$$
Which is always within half of one bit to the true value, as long as $z \leq e^n$. We simplify again with another convenient approximation:
$$\log_2\alpha \approx \log_2 z$$
Which is at worst one half bit below the true value. Since the probability of your condition holding is determined by $z$, and $\alpha$ is the ratio between the cardinalities of the output and input domains, the probability of your condition holding is approximately proportional to the size of the output domain divided by the size of the input domain. $\square$


Digital Signatures, Standard Hash Functions and MACs I'm studying Hash functions and Digital Signatures in sequence, and came up with some doubts about their usage.

First of all:

What is the difference between hashing a document and signing it?
And why aren't Standard Hash Functions considered fit for message authentication?

More specifically, considering Keyed Hash functions (MACs):

Are keyed hash functions (MACs) the mechanism on which Digital Signatures are based, or are they a way to implement a particular scheme of Digital Signature (e.g HMAC provided along with the message)?

Digital Signatures, hashes and MACs can do similar jobs.  They allow someone sending a message to a check value along with the message.  They allow someone receiving the message to verify that the message corresponds to the check value.  However, a hash is an unkeyed operation; anyone can compute the hash of the message.  So, while they provide protection against accidental message modification, they cannot provide any protection from an active attacker.

Digital signatures and MACs both ensure that someone in the middle (without the key) cannot modify a message without being detected (by the check value not validating).

However, even here still a difference; with a MAC, the sender and the receiver have the same key.  So, someone in the middle (without the key) cannot forge a message; however, the receiver can himself generate a message that validates.

With a digital signature, this is not the case.  The sender has a 'signing' key, and the receiver has a 'verification' key; the verification key allows the receiver to validate messages; however, he himself cannot forge any messages.

So, if the question is "should I use a HASH, a MAC (such as HMAC), or a digital signature", well, that depends on how much you trust anyone who does the validation.  If you just want to protect accidental changes to the message, well, a hash is fine (and doesn't force you to do the bother of key management).  If what you need is to protect messages from Alice to Bob (and so Bob is the only person who will ever validate a message with that key), then a MAC is appropriate (and a lot cheaper).  On the other hand, if you are posting messages to your blog, and you want everyone to be able to verify that you are the one posting, well, everyone will need the verification key, and so in that case, a digital signature is required.


When a program using openssl library is using a certificate, does the server check if the issuer(s) are still valid If I have a program acting as TLS server with a certificate signed by a CA, if one of the issuers in the chain becomes invalidated or the date expires, then how does the program using the certificate know this?  Or is it up to the client to do this checking?

My specific scenario is self-signed root CA signs server certificate.

The server may react as it pleases. The TLS spec doesn't come with application instructions in this regard.

The client should definitely reject any certificate chain it manages to build with an expired certificate. That means that the handshake should fail and the TLS session will not be instantiated. This requirement depends on a clock available to the client - which may be tricky in itself for certain environments.

It doesn't matter that the chain only consists of two certificates; root and leaf certificate.


What would be the most recommended AES && RSA Keys for production? While I am a front-end developer and not a security expert programmer, I am worry about the keys I am using for my AES && RSA encryption. Please help me to understand:

Is the following keys are secure ?
Is the following keys are performant and fast ?
I don't have any IV, is it good still without it ?
If IV is good and wont affect the performance then How can I add it ?

RSA KEY
KeyPairGenerator keyGen = KeyPairGenerator.getInstance("RSA");
keyGen.initialize(1024);
KeyPair pair =keyGen.generateKeyPair();
PrivateKey privateKey = pair.getPrivate();
PublicKey publicKey = pair.getPublic();

AES KEY
SecureRandom random = new SecureRandom();
byte [] key = new byte [16];
random.nextBytes(key);
SecretKeySpec secretKey = new SecretKeySpec(key, "AES");
cipher.init(Cipher.ENCRYPT_MODE, secretKey);

The RSA keys generated by the (Java) code in the question are 1024-bit, thus are not considered secure (even though there has not yet been any successful attack of a 1024-bit RSA key where that size was the only issue, see this). Security authorities no longer recommend anything below 2048-bit, and none that I know condones 2048-bit after 2030. Other common sizes (likely to remain safe sizably longer / against more powerful adversaries) are 3072 and 4096-bit.
The AES keys generated are 128-bit (since it consists of 16 random bytes and each byte is 8-bit), thus are appropriately sized to resist current attacks. There's consensus to consider them at least as secure as RSA-2048 when generated and used correctly. Other standard sizes are 192 and 256-bit, and give increased insurance, including against hypothetical Quantum Computers usable for cryptanalysis (which may or may not become reality before a global disaster makes earth unsuitable for human life).
It's impossible (and off-topic) to tell from the (Java) code linked if the key generators used are good or not. In particular, that depends heavily on the cryptoprovider used, which is tasked to allow use of a Smart Card or HSM. Even if the default Java cryptoprovider is used, it's quality depends on the particular JVM (including it's version), and the OS.
Practical security is also limited by many other factors. Among the most important are how the keys are stored or/and transmitted, and integrity of the platform the code runs on.

are these keys efficient?

For RSA: Yes, when it comes to use of the public key (encryption or signature verification), this is near best in class; no when it comes to use of the private key (decryption or signature generation). Other asymmetric algorithms are slower for public key, but considerably faster for private key. Yet beware that RSA is often more available. RSA is thus preferred when portability is paramount, or/and when public key operations dominate, e.g. signature of executable. ECC-based algorithms like EdDSA are preferable when available and there's an about even mix of public and private key usage.
For AES: Yes. AES-128 is typically one of the fastest symmetric-key algorithm available on a given platform.

I don't have any IV, is it good still without it ?

That's not answerable, for that depends on what good applies to. The key is still good. Using the key without IV can be anything from a disaster (e.g. for multiple AES-CTR encryption) to just fine (authentication).

If IV is good and wont affect the performance then how can I add it ?

An AES IV can be generated just like a 128-bit AES key.


Can Alice send Bob a secure message with only DSA and no key exchange? Suppose Bob has a DSA key pair, and Alice has Bob's public key. Is there any secure way that Alice can send Bob a message only he can read if Bob can not send any reply?

I think the answer is no, since DSA is only for messaging signing, so can only be used for things like authentication and Diffie-Hellman key exchange.

Let me first answer your actual question (and then I'll proceed to answer something slightly different that I think will be informative and helpful). Your question asks whether it's possible to use only a DSA key. Technically speaking, this is of course possible. The reason is that a DSA key has exactly the same format as an ElGamal key. No one forces you to use the key with the proper algorithm. (I know that this is a bit stupid, but it will be more meaningful after what follows below.) Just note that if you use the key both for DSA signing and for ElGamal encryption then you may have security problems, and you need to formally prove that this combination is OK. (By the way, this is all OK since Alice already has Bob's public key, so there is no problem of authenticating the key, etc.)

Despite the above answer, I have a feeling that what you are really asking is whether or not it's possible to use signatures alone in order to securely encrypt (in the public key setting, without a shared symmetric key). I'll translate it to "is it possible to use signatures alone to get key exchange" since key exchange is more relaxed than public-key encryption.

This is an excellent question. The first problem with the question is "how to formalize using one primitive to get another". The naive way of doing this is saying that if A exists then B exists. So, your question would be: is the following statement true "if signatures exist then key exchange exists". However, we believe that both signatures exist and key exchange exists, which if true, makes the statement logically true irrespective of any connection between signatures and key exchange. This led Impagliazzo and Rudich in their groundbreaking work Limits on the Provable Consequences of One way Permutations to define that one primitive implies another if one can be constructed from the other using a black-box reduction (and in a world where no other crypto exists, which can be achieved by giving the adversary an NP-oracle to solve all NP problems, for example). Note that most (but not all) reductions in crypto are black box. It is beyond the scope here to define black box, but for here it suffices to say that the primitive is used based on its input/output functionality only, and the reduction uses the adversary in a black-box way as well.

Now, back to your question. The answer is no. Impagliazzo and Rudich proved that one-way functions do not imply key exchange in this setting. Stated differently, it is impossible to construct a black box reduction from one-way functions to key exchange. Noting now that signatures can be constructed from one-way functions only (One-Way Functions are Necessary and Sufficient for Secure Signatures, Rompel), this implies that there exists no black-box reduction from signatures to key exchange. I remark that this result by Impagliazzo and Rudich holds in the presence of an eavesdropping adversary only, so it has nothing to do with man-in-the-middle attacks or anything like that.

Let's conclude by going back to DSA. Note that it is possible to use a DSA key to get key exchange; as I said, just use it for El Gamal. However, this is exactly the difference. My use of DSA is not black box. Rather, I am utilizing the number-theoretic properties and the structure of the DSA key. Thus, this does not contradict the result of Impagliazzo and Rudich.


Tampering with Shamir's subshares Suppose a set of Shamir's redistributable-secret-sharing participants issue a redistribution of subshares.

I envision this as a series of points on a line (2 of N, is planar, easy to think about).   Redistribution appears to create new lines that point to the heights of the original shares - but when the vectors are transposed they now can be used to derive points on a line that intersects the original key.

During redistribution, new indices can be chosen instead of re-using the same, there is no effect on the final values.  Imagine the actual indices chosen are not redistributed however, and instead a fixed value W is secretly added to each of the x-indices before transmission of the subshares.

Now the recipients reassemble the sub-shares, producing shares.   These shares will all lie on the same line, and will pass permutation based consistency checks.

But they will point to a different, essentially random, but consistent "secret".

The question is... can the recipient of these modified subshares determine what the original secret is?  From what I can tell, the effect of adding W depends on the random coefficients used during subshare redistribution, and should not be recoverable.

Normally the recipient could reconstruct... but with the fixed addition of W the recipient should receive... in essence ... the computation of a distributed hash function on W.

But I'm not sure.  If I graph this using 2 of 2, it seems like the recipient of the final shares, in order to deduce the original secret, would have to know the random coefficients used during each shareholder's redistribution.

Essentially I'm trying to create a distributed hash function.   I haven't found one that is "redistributable" the way shamir's secrets are.   Using a shamir secret, I can create a function ... and then add new members of the group and remove members of the group without re-rolling the original discarded secret.

Let $J$ be the set of conspirators and $S$ the total set of shareholders.

In general you are correct, provided the polynomial $A'(x)-A(x)$ is not zero at $x=0$, where

$$A'(x)=\sum_{j \in J} y_j \prod_{k \in J:k \neq j}
\frac{ (x+W- x_k)}{(x_j+W-x_k)}
\prod_{k \in S \setminus J}
\frac{ (x-x_k)}{(x_j-x_k)},
$$
and
$$A(x)=\sum_{j \in J} y_j \prod_{k \in J:k \neq j}
\frac{ (x- x_k)}{(x_j-x_k)}
\prod_{k \in S \setminus J}
\frac{ (x-x_k)}{(x_j-x_k)}.
$$

The equation can be simplified into $$A'(0)-A(0)=0$$ by letting $x=0,$ into a polynomial in $W$ whose roots you have to avoid if you want to obscure the secret from the innocent shareholders.

Since the difference is a Lagrange polynomial  it is as secure as ordinary secret sharing so if you aren't in possession of $W$, its effect is uniformly distributed over the finite field.


Storing encryption key? I am doing a password manager in Java. But now I am VERY confused because of the encryption. There will be the program login, where the user types its password, and it compares to a SHA512 hash. If it matches, the user logs in, if it doesn’t, then the user doesn’t login. I think there is no problem at this point.
And then, I am using AES to encrypt the user saved passwords. The user logs in, and then clicks on an "decrypt" button to decrypt his saved passwords.
My problem is, how am i going to do this? Because I thought for a bit, and... the decryption key must be saved somewhere. But it cant be in plain text... PLUS it needs to be exactly 16 chars long.
I created a thread on Reddit - http://www.reddit.com/r/java/comments/2awvjt/storing_encryption_key/
They give me several options, but none seems to be what I want. Why? Let's see 3 options a user gave me:

Store the encryption key. Not secure in the least

User has a password that is used to encrypt the encryption key - Pretty secure and usable

User has a private encryption key that you don't store. Very secure, very usable.

Well these are my opinions:

Obviously I’m not going to use that one, since the key will be stored in plaintext.

Well, I can hash the encryption key! But the hash must be stored somewhere! And its the hashed encryption key that’s going to be used to decrypt the user passwords... so I can use 16 chars of it. It is not user friendly if the user needs to set and remember a 16 char password! So i guess this is NOT secure

If I don’t store it, how am I going to decrypt it?

So, what can you suggest me?

First, using only a single SHA512 to hash the password is not enough.
You should use something like bcrypt with a long salt to store user password "hashes". A simple SHA512 can be attacked quite powerful with a dictionary attack, just trying millions of possible passwords and calculating the SHA512 hash for that until one matches.

Concerning the encryption of other users passwords.
Best would probably be to use a KDF (key derivation function) like PBKDF2 or SCrypt to derive a key (or keys) from that. These can be used to en/decrypt the stored user passwords.

But do not just apply e.g. AES directly to these passwords. Put the passwords in a suitable format e.g. XML or JSON and encrypt the serialized structure using a good AEAD scheme like GCM etc. Or use CBC but attach a MAC (HMAC or CMAC) to it. But always Encrypt-then-MAC !


Safe curves in Weierstrass form? I would like to implement a protocol using elliptic curves. I'm thinking of using MIRACL so using curves in their Weierstrass form is preferable as it they are supported by this framework.

I don't want to start picking random curves, so I am looking at the available safe curves. None of the curves is in Weierstrass form however. Do you have any suggestions for such curves? Even curves with low security, such as 80 bit curves are welcome.

Bernstein and Lange regard any curve in Weierstraß form as "not safe" because they assume, implementers of ECC with these curves will make stupid mistakes.
You can see a more detailed discussion on this point here:Safety of ECC-point addition.

So you should pick a subset of their criteria if you want the Weierstraß form(I don't see any reason not to). IMHO the most important criterion is that their creation was "stiff" i.e. there was no unexplained way to fill degrees of freedom in the creation process.
The NIST curves do not fullfill this criterion. They somehow fell from heaven and the community is suspicious. You might use the "stiffly" created ECC-brainpool elliptic curves(up to 512 bit), or my stiffly created curves ECC-curves_anders (up to 1024 bit).


Concatenating hashes I am thinking about to concatenate two hashes, but I was searched about this and I have questions, if some one should help me. Thank you

I have two strings str1 and str2 with variable large.
I need obtain a hash of these, but when I was searched I read about problems with collisions and I don't understand that.

In this moment I think that this is sufficient.

cipher = hash(str1) || hash(str2)

But according to other opinions is necessary add other injective function to prevent resistance collisions.
That approach looks like this:

cipher = hash(hash(str1) || hash(str2))

What do you think?

EDIT

I use murmur3 with 128.

I have many data and I need to represent this whit hashes, because that I use hash function.

With the time I use the first approach but many collisions have appeared and I don't understand why. I think because I use murmur3 of 128 to everything data or I don't know.

It is unclear what you are aiming for?
If you are trying to get a hash function collision resistent even in the face of a malicious adversary? murmur is no good regardless of concatenations.
You need to use a cryptographiclly secure hash such as something from the SHA-2 or SHA-3 families.

If you are talking about a non adverserial setup, murmur may suffice. But since modern cryptographic hashes have so fast implementations I usually recommend them anyway and have better piece of mind.

Regardless, both murur and the SHA families are defined on arbitraty length input so you can apply directly on concatenated input.

If you already have hashes, their concatenation(at double the output size) is at least as collision resistant as the underlying hash. The second construction at half the size also seems secure when a secure hash is used.


Role of long-term asymmetric keys in a forward secrecy instant messaging protocol? I am trying to understand how forward secrecy works in general, using a simple instant messaging protocol as an example. Tell me if I have this process right or not:

1) Alice and Bob each generate a pair of long-term public and private keys, then verify public key fingerprints in person. The ONLY thing these keys will be used for is for authentication (signing messages, and signing things during session key exchange). These keys will NEVER be used for encryption of any kind.
2) Alice and Bob use a key exchange algorithm such as Diffie-Hellman in the clear, using the keys from step 1 only to authenticate one another during this process. They end up with a shared session key.
3) Alice sends Bob a message, encrypting it with a symmetric cipher using the session key negotiated in step 2.
4) Bob decrypts Alice's message using the key negotiated in step 2.
5) The process repeats for each new message sent, starting from step 2. Step 1 is never repeated.

Forward secrecy (by generating new session keys) ensures that past communications cannot be decrypted if the long-term private keys from step 1 are compromised, however, masquerading as Alice or Bob would be possible going forward if this occurred, possibly compromising all future messages.

Where have I gone wrong here? Thanks so much in advance!

I don't think you are wrong on any of the points.

"Perfect forward secrecy" is a confusing name. Indeed it means that somebody who gets hold of one of the keys cannot use it to decrypt messages from the past.

There are two more properties you usually want:

When somebody does impersonate Alice or Bob as you suggest this should cut the real partner out of the conversation to make it detectable.
When somebody acquires a key he should not be able to decrypt messages after Alice and Bob have switched to a new key. Sometimes called backward secrecy.

There are probably more that I didn't think of right now and it case of group messaging it becomes even more complicated.
Dealing with these will make your steps (3.) - (5.) much more complex!


Is there a way to encrypt an integer within an arbitrary range? I need an algorithm that can take an integer, an arbitrary range, a key of 16/24/32 bytes, and an initialization vector of 16 bytes(ideally), and return an integer in the same range.
My latest attempt at this repeatedly encrypts an integer with AES_OFB until it is in the requested range. I'm using a stream cipher so that the ciphertext can be truncated without ruining the whole thing. The issue is that the decryption process sometimes halts too early.
Pseudocode:

data = 0x7234
range = 0x1000 to 0xa000 inclusive
data = aes_ofb_encrypt(data) // keystream "0x8d7c", data == 0xff48
0xff48 is not in the range, try again
data = aes_ofb_encrypt(data) // keystream "0xe5b7", data == 0x1aff
0x1aff is in the range
return data // 0x1aff

decrypting:
data = 0x1aff
range = 0x1000 to 0xa000 inclusive
data = aes_ofb_decrypt(data) // keystream "0x8d7c", data = 0x9783
0x9783 is in the range // halting too early!!
return 0x9783 // this isn't the right value!

Is there a better way to encrypt integers of an arbitrary range? Ideally I want it to be as strong as the AES algorithm. This example is obviously vulnerable to a brute force attack, but for cases where the integers are of or exceed 128 bits of length, I want the strength of the AES algorithm. Is this possible?

What you are asking is a straight application of Format Preserving Encryption, which builds ciphers which input and output are in a constrained format (generically: common to input and output, hence preserved). The FPE field has many articles with proven techniques; and proposed standards, including BPS and SP800-38G Draft.

Note: the method tentatively used in the question is not Cycle-Walking, and I do not see that it can be made to work if the cryptogram is kept of the form aes_ofb_encrypt(data); problem is, if the encryption algorithm made more than one try, the decryption algorithm will first make a decryption attempt that does not match anything that the encryption side made, and will occasionally conclude it reached the original plaintext, when it did not.

Here is a minimal solution (for integers of arbitrary size), using a simple variant of CTR (or OFB) mode.

Let $[A,B]$ be the interval (assumed public), and $k\in\{128,192,256\}$ the bit width of the AES key. Let $W=1+B-A$ be the (positive) number of integers the interval. Let $n=\Big\lceil{\log_2(W)+2k\over128}\Big\rceil$ be the number of 128-bit blocks to encode $W-1$ in binary plus $2k$ extra bits.

We'll define $X\bmod N$ as the unique integer $Y$ with $0\le Y<N$ and $X-Y$ multiple of $N$. We'll assimilate integers and bitstrings using big-endian convention.

From the $IV$, let both encryption and decryption generate a bitstring $S$ of $128n$ bits by enciphering $(IV+j)\bmod2^{128}$ for $j$ growing from $0$ to $n-1$, using the AES block cipher (equivalently: by enciphering $n$ blocks of zeroes in AES-CTR mode; using OFB mode would also work though not equivalently).

Given the plaintext $P$, let the encryption procedure output ciphertext$$C=((S-P)\bmod W)+A$$and given $C$, let the decryption procedure output$$P=((S-C)\bmod W)+A$$
Trivially, ciphertext is in the desired range, and plaintext is recovered by the decryption procedure. $S$ is indistinguishable from uniform on  $\{0,\dots,2^{128n}-1\}$, thus $S\bmod W$ is nearly uniform on $\{0,\dots,W-1\}$, with a very slight bias towards values below $2^{128n}\bmod W$, but so low that the adversary gains negligible advantage.


Bleichenbacher's Attack on high public exponent RSA keys? Why can't Bleichenbacher's Attack work for RSA public exponents with values equal to 65537 and above? Does the fact that 65337 is a prime number have any relevance to it?

Some attacks on some ad-hoc RSA encryption or signature padding, or/and their defective implementation, including several attacks due to Daniel Bleichenbacher, require an RSA public exponents $e$ of small value.

The limit has to do with some part of the padding (including a hash of $h$ bits), raised to the $e^\text{th}$ power, not being much wider than the public modulus $N$ of $n$ bits. It follows that $e\gg n/h$ block these attacks (but far from all attacks on ad-hoc RSA padding). There is no relation to $e$ being prime.

In RSA, ad-hoc padding should thus be avoided in favor of padding with reducibility to the RSA problem (like RSAES-OAEP, RSASSA-PSS, ISO/IEC 9796-2 mode 2 or 3), or schemes that do not need padding (like RSA-KEM). Security authorities recommend that for new applications, and $e\ge65537$ everywhere; see this for more.

Digression: Why 65537?

Using prime RSA public exponent $e$ is customary: it makes drawing randomly seeded primes $p$ with $\gcd(p-1,e)=1$ (as required in RSA) easier and less subject to implementation goofs.

Using $e$ of the form $2^k+1$ is customary: raising to such $e^\text{th}$ power reduces to squaring $k$ times, then multiplying once by the original number (including for operations modulo $N$ as in RSA).

Primes of the form $2^k+1$ are thus customary. They demonstrably all are with $k$ a power of two, and known as Fermat primes. With $h\ge128$ and $n\le16384$ in most practical uses of RSA, using for $e$ the fifth (and largest known or practically usable) Fermat prime $F_4=2^{(2^4)}+1=65537$ is always very much on the safe side w.r.t. matching $e\gg n/h$.


How does Microsoft's BitLocker Recovery Code work? I don't trust Microsoft BitLocker because it is closed source, which makes it so people can't audit it. But now I'm really interested in how its recovery code works. In my own knowledge, encrypted data can't be decrypted without knowing the key, but BitLocker breaks it.

So, I have three questions want to ask:

How does the recovery code work?
How can I implement a recovery code function on
any encryption algorithm in a mathematical way?
Will it be a possible backdoor/vulnerability to hacker?

In my own knowledge, encrypted data can't be decrypted without knowing the key, but BitLocker breaks it.

That description indicates you might have misunderstood something there. Bitlocker does not break anything* as Microsoft BitLocker uses recovery keys (read again: “keys”), not code! The related code for recovery is pretty similar to the usual decryption code which Bitlocker also uses when you’re using your personal key. No magic or backdoors there. For details, you might want to check “What is a BitLocker recovery key?” and “BitLocker recovery keys: FAQs” as well as the linked pages of the Bitlocker documentation.
The three sub-questions are partly too broad, and partly unanswerable completely for reasons I’ll gladly describe while trying to provide you with some helpful hints nevertheless…

How does the recovery code work?

You’ve already said it yourself when you wrote I don't trust Microsoft BitLocker because it is closed source, which makes it so people can't audit it. The words “Closed source” are important to remember when asking things like that. Long story short: I won’t break any intellectual rights for you and I’m pretty sure Microsoft will not be very willing to provide anyone with any legal right to do so unless it makes sense to them.
Yet, you could very well decompile the binaries on your own computer to check on its inner workings for yourself. Doing so enables you to engage in some personal auditing efforts too. Yet, your success in doing so will definitely depend on your decompiling abilities as well as your ability to read and understand the minimal ASM source that decompilers tend to spit out.

How can I implement a recovery code function on any encryption algorithm in a mathematical way?

This question is based on your misunderstanding that Microsoft Bitlocker “breaks” things with a recovery code. As noted above: that’s not how it works.
Microsoft BitLocker uses a recovery key – which is a special key that you can create when you turn on Bitlocker Drive Encryption for the first time on each drive that you encrypt. That recovery key is what enables Bitlocker to recover things for you when you – for example – forgot your usual (non-recovery) key… without a key, you won’t get anywhere – which is why Microsoft puts an emphasis on the fact that you should store the recovery key by printing it, saving it on removable media, or saving it as a file in a secure place.
Personally I would advise against storing secrets like keys on the same computer which you use to host/store your encrypted data. Yet, your security expectations may be different than mine. (More on the related, potential security impacts later when I answer your 3rd sub-question.)
The “code” that Bitlocker uses to recover data for you using that recovery key is pretty much the same as the code it uses when you decrypt things using your usual (non-recovery) key. The differences merely reside in detection of the key-type (regular or recovery) and handling/decrypting things accordingly. There is no magic or hidden unicorns in there… and Bitlocker is definitely not breaking any encryption when you recover an encrypted drive with your recovery key. Think of it as Bitlocker using regular decryption code as usual, merely the key-type is a different one… but a “recovery key” is nothing else than a regular key. It’s a secret to unlock your data in a worst-case-scenario; eg: you tried to memorize your key, but when waking up the next morning you realize you forgot it. That’s where you would need a recovery key, which you hopefully stored in a secure place at the time you created it – which was when you first encrypted the related disk/data.
So, could you implement such a recovery functionality no matter the encryption algorithm? Generally, yes. Just note that that would be more a “software feature” than an algorithm thing. Therefore, asking about a mathematical way to do so doesn’t really make sense as it’s too broad and practically impossible to cover all individual algorithms out there. And describing how to write secure wrappers around a crypt algo core can not really be described mathematically, as it’s more a programmatically thing and not “one mathematically describable formula to rule them all”. If an algorithm can encrypt and decrypt data based on a secret/key, nothing is stopping a programmer from wrapping a functionality around the crypto algo core to offer users an option to use recovery keys to decrypt things. (In case of doubt: I’m assuming such a programmer to have access to the crypto algo sourcode, or at least the API/SDK to be able do so… while ignoring some rare, rather borderlining situations where this might not be the case, yet possible to implement nevertheless.)
Surely, making two different keys decrypt the same data can be explained and described from a cryptographical point of view as there are several options/schemes available to do so. I won’t even start listing them here because Crypto.SE already has several Q&As handling that. The search-box at the top-right of every Crypto.SE page is the perfect tool to help you find them.

Will it be a possible backdoor/vulnerability to hacker?

A recovery key and related recovery functionality that expects you to enter such a secret before it is able to decrypt the related drive can hardly provide an attack vector unless you really messed up things badly from a security point of view. That’s one of the reasons Microsoft provided ample security advice made available to you as a user.
When thinking beyond that, I’ll have to say that anything is “possible“ if the circumstances allow it. So thinking beyond the obvious renders your question a bit too broad as you can’t possibly expect anyone to handle all the potential scenarios, situations, and potential security glitches you might or might not be thinking about.
To avoid such broadness, I’ll limit my answer to this sub-question by saying that when we assuming the decryption code doesn’t include a backdoor and/or vulnerability, the recovery procedure using recovery key(s) will hardly pose any risk as it mainly uses the same parts of the code Bitlocker also uses for the usual decryption functionality when using your usual (non-recovery) keys.
Whether a “hacker” can gain access to your encrypted drives as well as to the related keys and/or recovery keys ends up being something up for you to evaluate. As long as you keep your keys secure and use Bitlocker correcly (both thing are described in the related manual/documentation which Microsoft provided for a good reason), you should be fine.
Note that the Bitlocker documentation clearly states and advises not to store keys on the same machine hosting encrypted drives/data. If you decide to store keys and (encrypted) data in the same place anyway, you logically have to assume all related risks. Meaning: If an attacker can get access to your key storage (whichever key storage option you may have chosen), you’ll surely be inviting that attacker to walk all over all the encrypted data… if (and only if) that hacker is also able to gain access to the encrypted drives those keys belong to.
Assuming an average, non-state adversary and assuming you’ve followed the ample advice provided within the Bitlocker manual, that’s rather unlikely to happen.
For such an attack to work, an adversary would have to circumvent things like the Microsoft Firewall et al – which a security-aware person like you surely will have updated, correctly configured, and activated for your system protection. Attackers can’t read a single bit of any of any your drives (encrypted or not) unless they either circumventing those barriers (firewall et al) or when they have physical access to your drives.
Additionally, the attacker would also have to get access or knowledge of your keys. Repeating it again: if you follow the Bitlocker docs and contained recommendations, those keys won’t be stored on the same computer system and can therefore not be found on the same computer system that holds your encrypted drives. That makes things hard for an attacker as the attacker would also either need to circumvent other barriers (eg: firewall et al of other system), or be able to gain physical access to the keys.
Surely, things will turn against you if there are incidents like (eg) a burglar stumbling upon your encrypted drives as well as your keys which you’ve printed out but then put neatly into your desktop drawer next to your computer for everyone to find, or (eg) you store keys on another system within the same network but an attacker can access to both encrypted drives as well as the key storage after a successful full-network breach. If you think about it, a bit of human logic can prevent most of such risks… while the rest can be learned by reading the Microsoft Bitlocker manual and following the contained recommendations.
I think it is needless to say that, if you leave your system and/or network wide open (read: in an insecure state) and if you additionally ignore the manual/documentation by leaving at least one of your keys flying around within the reach of a potential attacker, your data could be decrypted without big efforts by near to anyone who is able to gain access to both the encrypted drives as well as related keys.
Wrapping it up:

Bitlocker doesn’t decrypted without knowing the key, so assuming BitLocker breaks anything by using some magic recovery code is wrong. Bitlocker uses recovery keys via related recovery functionalities. Every software out there that offers alike functionalities based on recovery keys works in a somewhat similar way – wrapping that additional functionality around a cryptographic algorithm core. Bitlocker doesn’t contain some magic sauce voiding your key by breaking its own crypto… it’s simply a recovery functionality based on recovery/backup keys. Without a key, Bitlocker won’t be willing nor able decrypt anything. How exactly this was implemented by Microsoft can only be answered in detail when having access to and studying the sourcecode. Even if this would be available, describing the details would break the limits of sanity as it would probably take a small book instead of an answer to talk about every detail of every related function and variable.

As with every encryption: if you store the encrypted data and the key on the same system – your data safety can be considered near to void. Anyone having access (or being able to gain access) to both encrypted data as well as related key(s) can access and decrypt your data. That’s one of the reasons why cryptographers, information security people, and the Bitlocker documentation itself advise to never store encrypted data and its related secret(s)/key(s) in the same location. As long as you keep keys out of reach of potential attackers by storing them in a separate, secure place (at least not on the same machine), the success rate of a potential “hack” and the ability of an attacker to read your decrypted data will be near to or equal to the success rate of a brute-force attack on your encrypted drives.
Actually, you could boil this whole thing down to a simple: “Securing your key(s) is your key to security.” – or, how others might know it: “Always keep your secrets secret.”

To learn about the Microsoft Bitlocker security recommendations related to key storage et al, and to clearly understand how Microsoft Bitlocker (including the recovery of encrypted drives) actually works, you might want to start reading the manual. The two links I provided at the beginning of this answer serve as a pretty good entry point to do so.
For your convenience, I’ll simple mention those links again: “What is a BitLocker recovery key?” and “BitLocker recovery keys: FAQs”. You’ll discover a complete manual when following those links, which will definitely be able to explain all this in more detail.

EDIT
Since the comments area showed there’s some confusion about the keys and which key en/decrypts what…
Each of those keys (both “regular” keys and “recovery” keys) can be used by Bitlocker. Practically it goes like this: You provide a key which will be used to construct the key-protector key (using a key derivation function – KDF). The output of the KDF is used to decrypt the Volume Master Key (VMK). The VMK is then used to decrypt the “Full Volume Encryption Key” (FVEK), which is the key that actually actually en/decrypt the individual disk/volume.
So, staying in line with the notation used in the comments:
$$\text{pin/recovery key} \rightarrow KDF \rightarrow VMK \rightarrow FVEK \rightarrow \text{volume en/decryption}$$


Is it safe to store AES encrypted string and the original string in plaintext next to each other? I have a server app that stores encrypted payload ($textPayload) that users encrypted on their side (The server is just stores is and serves it).
Users can use multiple encryption keys for different payloads ($textPayload)- the server doesn't know.
I am thinking about how to implement editing.
One approach I came up with was generating a random string ($editTokenPlain) on the client, encrypting it ($editToken) with the same key and storing both $editTokenPlain and $editToken next to the sensitive encrypted payload ($textPayload).
Then user would receive the edit token($editTokenPlain), encrypt it and send it together with the edited payload and if the encrypted token matched the encrypted value on the server - then the payload would be updated.
My question is: If I have 2 encrypted texts($textPayload,$editToken) with the same encryption key (using AES) and 1 decrypted text $editTokenPlain - can someone derive the encryption key?

What you're talking about is called a known plaintext attack, and any block cipher worth its salt will be resistant to it. So yes, it should be safe.


Use of Same Key for CTR and CBC-MAC in CCM Mode of Operation? The NIST Specification Document for CCM Mode of operation 800-38C states on Page 13

  The same key, K, is used for both the CTR and CBC-MAC mechanisms
  within CCM.

is it secure to use same key? or one should prefer two distinct keys. One for CTR Mode and other for CBC-MAC?

Basically you should never reuse a key and neither should you use CBC-MAC. CCM is considered secure because the designer knew about the issues of reusing a key and CBC-MAC length extension issues. The scheme is designed to be secure regardless of these issues.

In a general sense you should always use two keys unless you can prove your scheme to be secure regardless of the fact that the key is reused. The same goes for CBC-MAC, CMAC or HMAC should be preferred instead - CBC-MAC is only secure if the size of the message is known in advance and CCM does take this into consideration.

Also note that if changes are made to your scheme, e.g. supplanting CTR by CBC by another designer/developer then reusing a key may cause your scheme to fail spectacularly. So if you do decide to go this route when creating a secure scheme / protocol then make sure you document it thoroughly.

CCM is a cipher with it's own packet format. This makes it suitable for low level packet encryption / decryption where speed is important. The choice of one key and CBC-MAC was likely inspired by this. For a more generic authenticated cipher mode I'd recommend EAX mode or GCM mode instead.


Proof that the cardinality of the cipher text set is greater than or equal to the cardinality of the plaintext set for a symmetric cryptosystem I have been working on this problem and would appreciate some help
Consider a symmetric cryptosystem with non-empty finite sets $P, C, K$ of plaintexts, ciphertexts, and keys, respectively and with encryption functions $e_k : P \rightarrow C$ and decryption functions $d_k : C \rightarrow P$ indexed by keys $k \in  K$.
Show that $|C| \geqq |P|$

Here is my attempt:
Since $d_k$ is the left inverse of $e_k$ by definition of a cipher
Suppose $e_k(x) = e_k(y)$ then $x = d_k(e_k(x)) = d_k(e_k(y)) = y$ for $x \in P$ and $y \in C$
meaning $e_k$ is injective $\forall k \in K$
Also, $e_k(p) = c \in C, \forall p \in P$
Suppose, for finite sets $P$ and $C$, $|P| \gt |C|$
And, since both $P$ and $C$ are non-empty, then $|C|$ is at least 1 and $|P|$ is at least 2.
Then $\exists a,b \in P$ s.t $a \neq b$ and $e_k(x) = e_k(y)$ which raises a contradiction (as it would mean $e_k$ isnt injective)
Thus, $P \not\gt C$ i.e $|P| \leqq |C|$ or $|C| \geqq |P|$

The start of the proof, concluding $e_k$ is injective for all $k$, is fine. Only the ultra picky would add that $d_k$ is the left inverse of $e_k$ by definition of a cipher, and that the rest of that part considers $x$ and $y$ elements of $P$.
By my taste, the rest using proof by contradiction is on the overly complex and circular side, and less than rigorous: the "Then $\exists a,b \in P$ s.t $a \neq b$ and $e_k(x) = e_k(y)$" is not crystal clear (at least it it does not follow from a stated definition or theorem).
I would change the whole second part to: The cardinality of the destination set of an injection is at least the cardinality of it's source set, by definition of cardinality.
Or, if cardinality is not yet formally defined in the academic context: The size of the destination set of an injection is at least the size of it's source set, by a counting argument. The notion of counting argument is often invoked in crypto, in the context of hash collision, or proof of existence.
If we do want to make a proof by contradiction, one could invoke the pigeonhole principle, also common in crypto, on the tune of: $\lvert C\rvert<\lvert P\rvert$ and $e_k$ injective would contradict the pigeonhole principle.


Does cryptographically-secure pseudo random generators require a secure seed? For any cryptographically-secure pseudo random generators, do we need a secure random seed for those?
If the seed is predictable, then everything is broken due to the deterministic propetry of the algorithms.

Actually, your second sentence itself is the answer. A pseudo random number generator(cryptographically secure or not) is a deterministic algorithm which produce random looking numbers. Every time you provide the same seed it produces the same random looking numbers. Now, if your seed value is predictable and algorithm is public then the output of the deterministic algorithm is also predictable. So, the seed of a cryptographically secure pseudo random number generator must be secret, so that the output you get is unpredictable.


DH: Is it possible to solve for A private if all other variables are known with 90-bit modulus $g^{ab} \pmod{p} = B^a \pmod{p}$ where all variables are known except $a$. In this case, I have an equivalent value for $a'*b'$, but this is not the same as the real values of $a*b$ due to the modulus.
Everything else including the generator, the prime, $B$ public, the shared secret (or value of both sides of the equation) are known.
Since $p$ is a 90-bit value, this is would be difficult to calculate, but if there is some $\mathcal{O}(\sqrt{n})$ optimization, this may put it on the edge of the possibility to brute force.

Yes, this is totally feasible. Unless $p$ is purposely chosen as a safe prime, there's a good chance that's easy.
Computing $a$ given $B$, $p$, and $C=B^a\bmod p$ is a Discrete Logarithm Problem in the multiplicative group modulo prime¹ $p$, of order $r=p-1$.
For any DLP problem, there is a generic attack of cost a few times $\sqrt r$ group operations, Pollard's rho. Not only is $2^{\approx45}$ multiplications modulo 90-bit $p$ feasible, but that can be efficiently distributed on independent machines, see Paul C. van Oorschot and Michael J. Wiener's Parallel Collision Search with Cryptanalytic Applications (in Journal of Cryptology, 1999, following their article in proceedings of CCS 1994).
Also, there is the generic Pohlig-Hellman DLP method, which can help if $r$ is of known factorization.Here for we can factor the 89-bit $r/2$ in a breeze. The main DLP reduces to a few easier DLPs in groups of smaller prime order. These can be solved by Baby-step/Giant-step for small ones, or Pollard's rho and it's distributed variant for large ones. A typical factorization of $r$ has a largest prime factor $q$ of multiplicity 1 and much larger than other primes dividing $r$, so that the work is dominated by $\sqrt q$ group operations. Here, it is not told if $p$ was chosen such that $q=r/2$ is prime (which would make Pohlig-Hellman pointless), thus there is a fair chance that $q$ is sizably less than 89-bit, easing attack greatly.
There are even more efficient methods in the case of the multiplicative group $\mathbb Z_p^*$ that we target:

The index calculus algorithm. I'm not familiar with it, but would say it is likely the method of choice here if $(p-1)/2$ is prime.
The DLP variant of the General Number Field Sieve, which is the best known method for large $p$. The current GNFS DLP record is for a $795$-bit $p$ with $q=(p-1)/2$ prime (the hard case), see Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé, and Paul Zimmermann's Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment, in proceedings of Crypto 2020.

¹ The question's mention of Diffie-Hellman key exchange suggests $p$ is prime. If not, we can factor $p$ into $\prod{p_i}^{\alpha_i}$, solve for $a_i$ the problems $B^{a_i}\equiv C\pmod{{p_i}^{\alpha_i}}$, then use the Chinese Remainder Theorem modulo the ${p_i}^{\alpha_i-1}\,(p_i-1)$ to find a solution $a$.


Are there attacks that break collision resistance but not preimage resistance? Are there any examples of attacks on hash functions which:

break collision resistance and second preimage resistant, or
break collision resistance and preimage resistant?

I have looked at Rogaway's paper1, but it seems complicated, hence was wondering if a succinct example exists.

1) Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision-Resistance. Phillip Rogaway and Tom Shrimpton. Fast Software Encryption (FSE) 2004, LNCS vol. 3017, pp. 371–388, Springer, 2004.

Hash functions are usually designed to be both collision and preimage resistant. In practice, due to lower complexity, collision attacks usually come first. For instance, collisions for MD5 were theoretically constructed in 1996, and practically in 2004, whereas the first preimage attack with complexity 2^123 appeared in 2009 and has not been much improved since. MD5 could be considered preimage-resistant, but not collision-resistant at that time.

Attacks that violate collision resistance are usually based on differential cryptanalysis, whereas most of preimage attacks are based on the meet-in-the-middle principle.

It should be easy to construct artificial examples where either of properties is violated. E.g., the function F(x) = 0 for x=0,1, and F(x) = SHA-256(x) elsewhere - has trivial collisions, but most cryptographers would believe in its preimage resistance. In turn G(x) = x for even 256-bit x, and F(x) = SHA-256(x) elsewhere allows preimage recovery with probability 1/2, but it is likely to be as collision resistant as SHA-256 is.


How is public key cryptography used for digital signature? In public key cryptography, there are two different keys used for the encryption and decryption of data . I am wondering how it is used for digital signature

Aleksander's answer is very close, but there is one key difference between encrypting and signing a message.  When you create a digital signature, you are not encrypting the whole message.  The intent is only to validate that the message was indeed sent from you, not to prevent others from reading the message.

To sign a message, first a cryptographic hash is created.  This is a calculated string that provides a unique "fingerprint" for your message, that anyone can reproduce on the other end to validate that the message received is the same as the message sent.  This hash, rather than the message itself is what is first encrypted by the recipient's public key, then your private key, then it's appended along with the message as the signature and sent to the recipient.

The recipient must then use the sender's public key first, then their private key to decrypt the hash.  Once they have the received hash, the last step is to create their own hash of the message, and compare the two.  If the hashes match, the signature is valid, and everybody is happy!

Here's a great explanation: http://www.cs.utsa.edu/~bylander/cs1023/signature-encryption-example.html