Would A5/1 with a much larger state be a good choice of stream cipher for hardware? Would A5/1 with a much larger state be a good choice of stream cipher for hardware?  Assume that a reasonable choice of MAC is made such as GMAC, with the first 128 bits of the stream cipher output used as $H$ and the next 128 bits used to encrypt the auth tag.

I have argued so 15 years ago, and not been proven wrong since. Basically, A5/1, with a $n$-bit state, offers a resistance of roughly $2n/3$ bits of security. With $n = 64$, the resistance is very low, thus amenable to not only direct breaking, but also all kinds of trade-offs.

All the attacks published so far are dances around that resistance level of about 43 bits, the point being to make it so that actual instances can be broken "in real time": a 43-bit brute force can be done in relatively little time with a modern PC (in a matter of hours), but if you want to indulge in actual GSM spying you need a much faster break so that you can follow the target phone while it hops frequencies. Various methods have been proposed, that combine some possibly large precomputations with a wait for the algorithm to be in a state that is part of that precomputation; this is the idea in the original attack by Biryukov, Shamir and Wagner. Depending on the writing skills of whoever describes an attack, it is often possible to play between elementary operations, bit operations, CPU opcodes and other measures to get the complexity figure as low as possible, e.g. down to $2^{40}$ for A5/1, but that's just marketing.

At its core, there is always the brute force on the clocking sequence: you need to guess two clocking bits, one way or another, to inject one bit of known output.

As such, an A5/1-like design boosted to a 192-bit internal state ought to offer a resistance of about "128 bits" and, to my knowledge, would not be substantially broken -- as far as we know. One might need to expand the size a bit (say, to 210 bits) to avoid academic trickeries resulting in attacks in cost $2^{126.3}$ or similar nitpicking. How many "blank rounds" should be run after injecting the key is an open question (the original A5/1 runs 100 blank rounds).

Though an "extended A5/1" would be implementable in hardware with very few gates, it would not have been extensively reviewed, and experience shows that extensive review is not optional in the design of cryptographic algorithms. As such, it cannot be recommended "as is". I suggest that you consider instead using one of the eSTREAM portfolio algorithms, especially those that follow the "hardware profile". In particular, MICKEY 2.0 has a variant with a 128-bit key.


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

I can't find any information on this and I really want to know. We discussed in class number theory and after making some proofs on division algorithms we made some modular arithmetic. It is my understanding that the definition of addition modulo $2^{32}$ is: $a +_n b = (a + b) \bmod (n)$.

So if I were to have for example 27 added to 8 modulo 32, I would have something like $(27 + 8) \bmod (32) = (35) \bmod (32) = 3$.

Is this right?
Is this the same hashing algorithms talk about when mentioning addition modulo $2^{32}$? Why can't I find this anywhere?

Why isn't there a Wikipedia article with details on the addition modulo $2^{32}$ that is talked about on cryptography?

I ask if this is the same hashing algorithms talk about because in my understanding, this answer here says that in Java addition modulo $2^{32}$ is the same as simply writing "+", but I don't think a simple sum can possibly be the same. I'm totally lost.

In cryptography, addition modulo $n$ (where $n$ is a positive integer, maybe $n=32$ as in the original question, or $n=2^{32}$ as in the revised question) is usually understood as the application from $\mathbb Z\times \mathbb Z$ to $\mathbb Z$, $(a,b)\mapsto c$ with $c$ such that $0\le c<n$ and $(a+b-c)$ is a multiple of $n$. That's also a common sense in math, although there the result could rather be in $\mathbb Z/n\mathbb Z$ (recall $\mathbb Z$ is the set of signed integers, whereas $\mathbb Z/n\mathbb Z$ is the set of equivalence classes of the relation: equal modulo $n$).

We may write $(a+b)\bmod n=c$ using \bmod in $\TeX$. This implie $a+b\equiv c\pmod n$ using \pmod in $\TeX$, but only the former restrict $c$ to be in range $[0\dots n-1]$.

When the modulus $n$ is the $k$-th power of $2$ ($n=2^k$), addition modulo $n$ is also called $k$-bit addition. Thus, addition modulo $32$ is the same as $5$-bit addition, and addition modulo $2^{32}$ is the same as $32$-bit addition.

Often, in cryptography, we assimilate numbers to bitstrings, and the output $c$ of the operator is not a number, but rather a bitstring representing $c$ in base $2$ (over exactly $\lceil \log_2n\rceil$ bits and most significant bit first unless otherwise stated).

Thus the result of addition modulo $32$ of $27$ and $8$ is the integer $3$, or the bitstring 00011, depending on context. And the result of addition modulo $2^{32}$ of $2000000000$ (0x77359400) and $3000000000$ (0xB2D05E00) is $705032704$ (0x2A05F200) or the bitsring 00101010000001011111001000000000, because $5000000000-705032704=2^{32}$.

Sometime the inputs $a$ or $b$ of the operator are restricted to be non-negative, or/and less than $n$, or/and bitstrings, perhaps of fixed or limited size. Sometime the output range for $c$ is $-n/2\le c<n/2$ rather than $0\le c<n$ (e.g. for implementation of 32-bit addition in contexts lacking unsigned 32-bit type, see below). YMMV.

There is a Wikipedia entry on modular arithmetic which is a better introduction to that subject, but lacks the specialization to crypto and discussion on bitstrings.

The following discussion is exclusively about Java (except for restrictions of the language in some Java Cards, which may not support type longor even int), and thus somewhat off-topic here, but well.

When working with variables of type long (also int, short, byte) (a+b)&0xffffffffL is the sum of a and b modulo $2^{32}$ in the cryptographic sense, and of type long. That &0xffffffffL technique works for operators + - * & | ^ ~ (but not % /). It can be extended to any modulus $n=2^k$ with $0\le k\le63$ by adjusting the constant, which is $n-1$. Further, when $0\le k\le31$ we can remove the L, and if both a and b are of type int, shortor byte, the result will be of type int.

The definition of operators + - * & | ^ ~ (but not % /) operating on int variables is such that you can get along with assuming these operators work modulo $2^{32}$ as defined in cryptography, except that numbers in range $[2^{31}\dots 2^{32}-1]$ are represented as a negative int in Java. This makes code clearer, simpler, faster, and (for arrays) conserves memory. That technique is used because, before Java 7, there was no unsigned type in Java.

For n of type int in range $[1\dots2^{31}-1]$ and operands a and b of type int in range $[0\dots2^{30}-1]$, (a+b)%n is the sum of a and b modulo n in the cryptographic sense, and of type int. This does not hold for the full range of input operands for two independent reasons:

when the left operand of operator % is negative and not a multiple of the right operand, the result is negative;
(a+b) is defined to be the integer $c$ with $-2^{31}\le c<2^{31}$ and $c\equiv a+b\pmod{2^{32}}$, from which it follows that sometime $(\mathtt{(a+b)\%n})\not\equiv (a+b)\pmod n$ (though that second issue can not occur when $n$ is a power of two, including for $n=32$).

Notice that, except for educative/testing purposes, it is seldom a good idea to implement a cryptographic primitive in Java: in production, one should use more efficient primitives called from Java.


FIPS 113 Computer Data Authentication on the NIST website for Message authentication There is a mention of 2 approved algorithms, i am curious about the first one. the link to FIPS 113, Computer Data Authentication appears to be dead since it redirects me to the homepage of NIST.gov

On a dutch Wikipedia article (the only wiki article i could find about FIPS 113, it is stated this FIPS is outdated and not secure by today's standards. Is this true? is the Algorithm described in FIPS no longer safe? would this make HMAC the only NIST approved MAC?

I have written an email notifying the NIST site administrator about the link.

The NIST site http://csrc.nist.gov/publications/PubsFIPSArch.html lists FIPS 113 as Withdrawn: Sep 2008. The Federal Register https://www.federalregister.gov/articles/2005/07/15/05-13992/proposed-withdrawal-of-ten-10-federal-information-processing-standards-fips gives a reason:

  FIPS 113, Computer Data Authentication, specifies an algorithm for
  generating and verifying a Message Authentication Code (MAC). Since
  the algorithm is based on the Data Encryption Standard, which has been
  recommended for withdrawal, NIST plans to recommend the use of newer
  techniques for data authentication based on more secure algorithms.


Multiple private keys with RSA Say I want generate pair of public/private keys. First of all lets choose two prime numbers $q = 17, p = 11$. Now, lets choose public key $e=7$ and try to determine the matching private key $d$:
$$d\cdot e \mod (q-1)(p-1) = 1$$
$$d\cdot 7 \mod 16\cdot 10 = 1$$
$$7d \mod 160 = 1$$

So, there are many solutions for this equation, such $23$, $183$, $343$ and in general $d = 160k+23$ for every $k\in Z$.

But RSA should have single private key for public key, so why can I get many solutions/private keys? I tested them, and they can decrypt the encryption of the public key $e$.

I know that $q$ and $p$ should be destroyed and without them it is hard to calculate the private key. I just don't understand why there are many private keys for one public key...

Well,

You're working in the multiplicative group.
There is a theorem (which is proven by group axioms), that the inverse element is unique ($d$ is inverse to $e$).
When you say $d = 160 \cdot k + 23$ for every $k$ from $Z$, you actually should mean that in the context mod $160$ then your $d \cdot k$ for any $k$ is actually the same element.

I think the mindtrick here is that:

You claim: $d = 160 \cdot k + 23$ for every $k$ in Z; oh, there is a lot of such elements!
NO. You're in the multiplicative group. You can write this element different ways. But it is still the same element.

You do not work with "numbers". You work with an element of multiplicative group. Which can be represented many ways (see your claim about $k$). But it's the same element. In the context of 'multiplicative group mod $160$, elements $23$ and $183$ are the same elements.

You can easily prove that $23 \bmod 160 = 183 \bmod 160$. So $183$ equals $23$ in group mod $160$. That means you can write on sheet of paper $183$ or $23$ or whatever $160 \cdot k + 23$ you like, and you will be talking about the same element, which is unique.

The key is therefore also unique - your key is an element of a multiplicative group, which can be written in many ways ($160 \cdot k + 23$, where $k$ is in $Z$)


How can I prove I have a certain Facebook account by signature? I would like to know how to prove I have certain Facebook account (or that I can login to that account).

You have to show that you can use the account. You cannot prove it offline, without accessing the account (or storing public information there) or else anyone else could produce the same "proof".

Normally proof of ownership of a web page is done by the other party producing some random value and you publishing that value on the page. That would work here too. Alternatively, since Facebook accounts double as email, the other party could send a random secret by email to the @facebook.com address of that account, which the supposed account owner would have to find out. (Plain email is often not really a very secure transport, though.)

If you insisted on using asymmetric cryptography, you would have to publish a public key using that account. Then you could prove ownership of the corresponding private key by producing signatures using it. This would have the advantage of only needing to publish the key using the account once.


Hash match vs PGP to ensure integrity What is the difference? I found it quite hard to check for integrity using Gpg4win. Checking for hash was easy with Online MD5 & SHA1 Hash Generator For File. Is there any advantage to use Gpg4win? I often see that software developers leave their PGP and signing keys for verification and quite few leave a hash for that purpose. Why?

Yes, there is a lot of difference, although it depends on how the software is produced and published as well.

With a hash you can just check if the file - as downloaded - is correct. For instance if you retrieve a file through a mirror or torrent then you might get a different file than you asked for. Validating the hash on a controlled site by the owner can then assure you that the file is correct. Of course you'd want a different hash than MD5 and SHA-1 is not secure anymore either - SHA-256 is often used instead. However, if an attacker can replace that hash then you're still vulnerable; all it takes is to compromise the site hosting the hash; anybody can calculate a hash over any file after all.

If there is a signature over the file, and you can trust the public key of the developer, then you can just verify the signature. An attacker cannot create a valid signature even if the hosting site of the signature is compromised. In general the key is kept secure with the developer team rather than the persons available for the hosting of the signature.

That's not to say that signatures are a panacea. Establishing the trust of the public key can be tricky and the security of the signing key or signature generation service may not be up to par. For instance, Microsoft authenticode keys have been misused in the past.


If someone had a list of all primes, would it be possible for them to factor any integer in polynomial time? For example, if they somehow got a function that would churn out any arbitrary amount of primes in a row. Could they break the RSA problem then?

Mathematically, yes, it will work. Practically, you will require an extremely very long time and an incredible amount of energy, considering the sizes of the primes  involved in RSA (usually around 1024-bit prime numbers). It is about billion and billions of years and billions and billions times the energy of the whole universe (RSA: How effective is this keypair-trash attack)


Doubt about published test vectors for gimli hash In https://eprint.iacr.org/2017/630.pdf and https://gimli.cr.yp.to/gimli-20170627.pdf there are test vectors for the gimli hash function. I have compile the reference C code test_hash.c from https://gimli.cr.yp.to/gimli-20170627.tar.gz on two systems (Intel x86/Win, ARMV7l GNU/Linux) and consistently get results that differ from the printed vectors. The paper lists e.g.

input: "" (empty string)
input (bytes): (0 bytes)
output:
bd2a1b1cdab81f9fea9d5fd513372ab9d1481428385de2b2d3571d8504fdd703

but both executables give

b0634b2c0b082aedc5c0a2fe4ee3adcfc989ec05de6f00addb04b3aaac271f67

  Has anybody verified the test vectors from the papers?

For the permutation/compression function test program test.c my results are the same as given in the file test.exp.

I'm one of the authors of Gimli.

TL;DR: Test vectors provided by the paper are indeed wrong.

We had a error when we generated the paper and the test vectors have not been updated with respect to the last iteration of Gimli (in development stages).

Also one of the test vectors had a double space at some place. This has been corrected and will be updated in the revision of the paper.

Please find the correct ones below:

Test vectors

input 1:

  There's plenty for the both of us, may the best Dwarf win.

54686572 65277320 706c656e 74792066 6f722074 68652062 6f746820
6f662075 732c206d 61792074 68652062 65737420 44776172 66207769
6e2e

output 1:

4afb3ff784c7ad6943d49cf5da79facfa7c4434e1ce44f5dd4b28f91a84d22c8

input 2:

  If anyone was to ask for my opinion, which I note they're not, I'd say we were taking the long way around.

49662061 6e796f6e 65207761 7320746f 2061736b 20666f72 206d7920
6f70696e 696f6e2c 20776869 63682049 206e6f74 65207468 65792772
65206e6f 742c2049 27642073 61792077 65207765 72652074 616b696e
67207468 65206c6f 6e672077 61792061 726f756e 642e

output 2:

ba82a16a7b224c15bed8e8bdc88903a4006bc7beda78297d96029203ef08e07c

input 3:

  Speak words we can all understand!

53706561 6b20776f 72647320 77652063 616e2061 6c6c2075 6e646572
7374616e 6421

output 3:

8dd4d132059b72f8e8493f9afb86c6d86263e7439fc64cbb361fcbccf8b01267

input 4:

  It's true you don't see many Dwarf-women. And in fact, they are so alike in voice and appearance, that they are often mistaken for Dwarf-men. And this in turn has given rise to the belief that there are no Dwarf-women, and that Dwarves just spring out of holes in the ground! Which is, of course, ridiculous.

49742773 20747275 6520796f 7520646f 6e277420 73656520 6d616e79
20447761 72662d77 6f6d656e 2e20416e 6420696e 20666163 742c2074
68657920 61726520 736f2061 6c696b65 20696e20 766f6963 6520616e
64206170 70656172 616e6365 2c207468 61742074 68657920 61726520
6f667465 6e206d69 7374616b 656e2066 6f722044 77617266 2d6d656e
2e20416e 64207468 69732069 6e207475 726e2068 61732067 6976656e
20726973 6520746f 20746865 2062656c 69656620 74686174 20746865
72652061 7265206e 6f204477 6172662d 776f6d65 6e2c2061 6e642074
68617420 44776172 76657320 6a757374 20737072 696e6720 6f757420
6f662068 6f6c6573 20696e20 74686520 67726f75 6e642120 57686963
68206973 2c206f66 20636f75 7273652c 20726964 6963756c 6f75732e

output 4:

8887a5367d961d6734ee1a0d4aee09caca7fd6b606096ff69d8ce7b9a496cd2f

input 5:

 no bytes

ouput 5:

b0634b2c0b082aedc5c0a2fe4ee3adcfc989ec05de6f00addb04b3aaac271f67


Does threshold crypto (m-of-n) guarantee that m peers discover the plain text? In a threshold cryptosystem, is there any guarantee that all $m$ peers participating in retrieving a plain-text will all retrieve it? If not, is it possible to provide such a guarantee?

For instance if the $m$ peers are hostile to each other, is there a way to either have none of them get the plain text, or all of them?

The terminology for what you are describing is called fairness. This comes up often in threshold cryptography. Just knowing the right terminology should help you find many papers on the topic.

In general, fairness is impossible unless there is an honest majority [Cleve1986], though some non-trivial functions can be computed [Gordon2008a, Gordon2008b].

You appear to be most interested in fair threshold decryption of a ciphertext.

The paper Fair threshold decryption with semi-trusted third
parties provides a construction that assumes semi-trusted third parties are available to help. Section 1.1 of that paper, provides a good intro to the related work and some of the different assumptions or paradigms that have been used.


Generate random number which should depend on key i want to generate random number for example from [1..100]. The algorithm which would generates random number should work similarly like a "Linear congruential generator", like this:

$X_{n+1}≡(aX_n + c)\ (mod\ m)$

Where:
$c$ - increment should be something like 98979817
$a$ - should be used for security and should be great number
$X_n$ - initial number

However, I can't use this formula because my $m\ (mod m)$ is 100 so it's $m < c$ and $m < a$. While it should be $m > c$ and $m > a$.

Maybe there is something similar which is more secure than this?

Any Pseudo Random Number Generator using a Linear Congruential Generator, and no cryptography, is going to be unsafe, or at the very least unsatisfactory, per the criteria in our FAQ. Likely, a skilled adversary would be able to predict future output from some amount of past output with moderate work; at best, that won't happen, but there will be no sound argument that it is not possible. There are many more or less difficult to read papers making that point. A recent question, another there, further illustrate this. If the more secure requirement is to be taken any seriously, it is best to forget the LCG entirely, and use cryptography.

There should be three steps in a secure "Random Number Generator depending on a key" producing an output sequence uniformly distributed on the integers in $[1…100]$:

Stretching of the initial key. The purpose is to make brute force search of the key infeasible, or at least costly. That is superfluous if the key is already both wide enough (say 120 bit or more; 256 is aplenty) and chosen uniformly at random; in almost any other case, including when a human is expected to remember (or worse choose) the key, a deliberately slow transformation of that input is highly recommended. In many cases (notably: the combination of multiple users and use of password), the initial key should be salted while stretched. The standard building block for these functions is a Password-Based Key Derivation Function. A common one is PBKDF2; Bcrypt is much safer; the current state of the art is Scrypt.
A Cryptographically Secure Pseudo Random Number Generator, or equivalently the Keystream Generator of a secure Stream Cipher. We'll feed it the (possibly stretched) key (in the input named seed or key), and then it will output on demand practically any number of random-looking bits that we may want. The design of that cryptographic primitive strives to make that output computationally indistinguishable from random by an adversary not knowing the seed. There are a plethora of CSPRNG and Stream Ciphers to choose among, and the best choice depends on context. If it must be fast on any modern CPU, Salsa20 comes to mind.
Post-conditioning to obtain outputs uniformly distributed on the desired output interval $[u…v]$, here $[1…100]$. One simple suitable technique (slightly wasteful, but that does not matter since the CSPRNG is likely fast) is to:

Find the lowest integer $w$ such that $2^w\ge v-u+1$; here that is $w=7$, since $128\ge100$.
Obtain $w$ bits using the CSPRNG, forming an integer $r$ in range $[0…2^w-1]$, until $r<v-u+1$ (otherwise, discard $r$ and repeat this step).
Output $u+r$, and proceed to the previous step as needed to obtain more output.

If being simple and based on a LCG is important, and being secure is pointless as long as the output is good enough to pass some simple statistical test, the following procedure builds a LCG and post-condition its output (I assume the range $[u…v]$ has width no more than about $2^{16}$).

Choose $m=2^{64}$ (or a convenient higher power of $2$), $a=3141592621$, $c=1$ (this conforms to more detailed advice in TAOCP Volume 2, section 3.6; except that I kept $a$ unchanged, rather than taking the risk to scale it with $m$); the C or C++ type unsigned long long, if available, is suitable for implicit reduction modulo some appropriate implementation-dependent $m$.
Find $w$ from the interval $[u…v]$ as above (here $w=7$ for $[1…100]$).
Set $X$ to the key truncated to the bit width of $m$ (Repeat: security is out of scope! But still, it does not harm to feed other key bits in $c$, as long as it is forced to be odd).
Set $X$ to $a⋅X+c\bmod m$; in C that's X = a*X+c;.
Form $r$ in range $[0…2^w-1]$ from the $w$ high bits of $X$; in C that's r = X>>(W-w); where W is the bit width of the unsigned integer type chosen for X, and $m=2^{\mathtt W}$.
If $r\ge v-u+1$, proceed to step 4.
Output $u+r$, and proceed to step 4 as needed to obtain more output.


Would increasing the "target space" of MD5 collisions make it significantly easier to find a collision? This is tangential to this question, which asks about generating a file to match an exact MD5 hash.
My question is if it would be significantly easier to generate a file that is "within X digits of" an existing MD5 hash.
For example, if this is the MD5 hash I am trying to copy:
5f4dcc3b5aa765d61d8327deb882cf99
I would find these results acceptable as a 'copy' (differences are bolded):
5f4dcc3b5aa765d61d8327d5b882cf99
5f4dccab5aa765d61d8397deb882cf99
5f4dcc3b5aa765d61d8345debe82cf99
They are different, but without the bolded text would be difficult to detect with the human eye.
Does this significantly reduce the amount of time it would take to create an MD5 collision, given a hash, or is it on the same order? To say it another way, the fastest I was able to find was 2^24.1 (page 5), would having a larger "target space" significantly decrease this?

Note: The attacks you refer to in that thesis are structural attacks, I will consider the complexity of a brute force attack, which would be applicable to any hash function $H$ which is well designed, approximating a pseudorandom function. There are some good answers here on the complexity of the birthday attack on a hash function, which is $O(2^{n/2})$ for an $n$-bit hash output.
Let $b$ be the number of bytes and $n=8b$ be the number of bits in the output of $H.$ It seems to me that you are happy for the hex output to be "almost correct". So we should consider the $2b$ output nibbles in $\{0,1\}^4$ and say that the output is almost $f-$correct if there are up to $f$ nibbles that are different than the output you are trying to get near to. For your examples, $f=2.$
The crucial thing is to identify the size of your 'target space', which is
$$
T:=2^{4}\sum_{j=0}^f\binom{2b}{j},\quad\quad\quad\quad(1)
$$
since there are $2^4$ nibbles. Now, $T=2^4(1+2b+2b(2b-1)/2)$ or $T=2^4(1+b(2b+1))|_{b=16}=8464\approx 2^{13.05},$
which gives attack complexity (via the birthday paradox) of $$2^{(128-13.05)/2}\approx 2^{62.5}$$
for the pairwise XOR of any two outputs of the hash function to be in $T.$
However, this is not quite enough, if what you want is to be near a given fixed hash output as opposed to be near any of the outputs so far (so you want a near preimage as opposed to a near collision). If it is the latter, then proceed as below.
The probability that you miss the fixed target for $k$ randomly chosen inputs is
$$
p(f,k)\geq \left(1-\frac{T}{2^n}\right)^k =\left[\left(1-\frac{1}{2^n /T}\right)^{2^n/T}\right]^{Tk/2^n} \sim \exp[-Tk/2^n]
$$
which is only a lower bound but accurate for small $f.$ The reason we can't proceed as in the birthday paradox writing
$$
\left(1-\frac{T}{2^n}\right)\left(1-\frac{T+1}{2^n}\right)\cdots\left(1-\frac{T+k-1}{2^n}\right)
$$
for the probability is that we may be colliding with a previous hash output but this output may not be in the target set.
If we make the product $Tk=2^n,$ then we can have a probability of success of $1-e^{-1}\approx 0.63$. Since $T=2^{13.05},$ we need to perform no more than (and probably somewhat less than)
$$
2^{128-13.05}=2^{114.95}
$$
hash computations.
If you are happy with larger $f,$ then use the dominant term in (1) to obtain
$$
T\geq 2^4 b(2b-1)\cdots(2b-f+1)
$$
for a good approximation to $T$ but the direct computation of exact $T$ is not hard either.


Finite fields in elliptic curve I have an elliptic curve defined over finite field where $S_1=aP$ . Is it valid to say that $S_1P$ can also be computed.  $P$ is the generator of the group.
What my real question is that. Should '$a$' be always an integer or can it be a group element itself??

Should '$a$' be always an integer or can it be a group element itself??

Well, $aP$ is defined to be:

$aP \equiv \underbrace{P + P + \ldots + P}_\text{a times}$

From that definition, we see that this makes sense only if $a$ is an integer; it needs to be a count of the number of $P$'s to add together.


public key delivery without third party I am currently working on an anonymous P2P file sharing application and I am elaborating some already existing solutions. Some of them allegedly provide point-to-point encryption using RSA public/private keys to exchange a symmetric secret key, which is then used to encrypt a stream of data.

But I wonder how is it possible for two peers to safely exchange their public keys with each other without any third party (without any Certificate authority providing those public keys) and at the same time without being able to become attacked with "Man-in-the-middle" technique? (Actually some of them allow exporting generated public keys and exchange them in a "secure" way like personal meeting, phone, e-mail. But most of these P2P solutions communicate only over the wire. )

By point-to-point I mean connection between two peers, who are directly connected nodes in an P2P overlay, but can be more than one hops away from each other in a physical network.

You will always need to have some way of identifying the other party, be it a pre-distributed key or out-of-band procedures as you are describing. There is no purely digital method that can do this without some kind of shared knowledge.


Initialization value (IV) bit error When a bit error happens in an IV, what would the result of decrypting a cipher-text be in the different encryption modes like ECB, CBC, CFB, OFB, and CTR?

This seems a strange question to ask. Is it for an assignment or are you trying to select the best mode for a particular application? Regardless:

ECB does not use an IV.
CTR has a nonce value, which could be considered an IV. A bit error there will produce an entirely different key stream for every block.
CBC and CFB will corrupt the first plaintext block, but thereafter it is OK.
In the case of OFB, I believe the entire plaintext will be corrupted because the entire stream of data is determined by the IV (plus the key, of course).


AES-XTS vs AES-CTR for Write Once Storage I have a disk on which each sector can only be written once (like a journal, only appending is possible). Unused sectors are reported as being filled with zeroes, while used sectors should not be readable without authentication (achieved over a separate channel with the drive).

Since an attacker can never gather two ciphertexts for the same block, is there any advantage of using AES-XTS over AES-CTR? If not, should I still use AES-XTS, since it makes it clear that we are effectively dealing with FDE (although in a write-once fassion) and reviewers might (correctly) argue that CTR should not be used for FDE? Or should I use AES-CTR, because its security guarantees are proven better?

The goal is to make it possible to send the encrypted data to the manufacturer (who also holds the key) in case the password is lost to allow data recovery (which is a regulatory requirement). Each disk uses a unique key.

EDIT: this is not a duplicate of Why do we use XTS over CTR for disk encryption?, because I am concerned about write-once storage, not a regular disk drive that will be overwritten with different data regularly, thus the attack surface is very different.

Analyzing the risks and correctly setting the threat model is important when choosing the encryption schemes.

If the attacker is a passive attacker, that he can only read the hard disk while transmitted, as it pointed out in the comparison of the XTS vs CTR question, there is no benefit against for passive attacker.

When the attacker, however, is an active attacker you will need authentication. CTR and XTS modes are not authenticated encryption modes. In CTR mode, when the attacker modified a bit the ciphertext will turn into a valid plaintext. It is also possible in  XTS mode, a little harder to achieve. To mitigate, you can hash the whole disk and then apply a digital signature on it. The signature can be transmitted over another channel.

You can see a discussion here Why not authenticate full-disk encryption? about integrating the authentication into a filesystem.


Optimising shor's algorithm So I've run into this challenge where I was given the guess $g$, and the power $p$ of Shor's algorithm.

All I have to do now is $g^{p/2} - 1$ and then GCD the result with n. But the problem is computing $g^{p/2}$ takes a RIDICULOUS amount of time, even with the exponentiation by squaring method.

Is there any possibility to optimize this process? Or at least is there a better way to compute $g^{p/2}$?

Note: g and p are both of the order of 40 digits or so, and I was doing the exponentiation by squaring using python 3.7

I believe that the python built-in pow(g, p/2, n) does what you want fairly quickly...


Is there a name for encrypting a decimal number using a one time pad? I asked a question somewhere else on stack exchange and had to put something like "using the numerical one time pad the user can create their encrypted message by hand". Is there a better way of saying "numerical one time pad"?

The following is an example of what I'm trying to describe:
key:                                 7 1 6 3 1 3
message:                             0 5 0 9 9 9
ciphertext = (message + key) mod 10: 7 6 6 2 0 2

Most OTP examples use mod 26, and most computer programs use mod 2 (XOR), but I'm trying to describe encrypting a decimal number specifically.

The correct names are OTLP (one time letter pad) and OTFP (one time figure pad). More about the system here:

http://users.telenet.be/d.rijmenants/en/onetimepad.htm


Could the Enigma algorithm be classified as a Feistel network? The Enigma algorithm is a encryption method that was developed (I believe) by the Germans in WWII. It went a little something like this:

When a letter was typed on the keyboard of the Enigma machine, it was first sent through the first rotor, which would shift the letter according to its present setting. The new letter would then pass through the second rotor, where it would be replaced by a substitution according to the present setting of the second rotor. This new letter would in turn pass through the third rotor, again being substituted accordingly. Next, this new letter would be bounced off of a reflector, and back through the three rotors in reverse order. The trick that made Enigma so powerful for its time though, was the spinning of the rotors. As the plain text letter passed through the first rotor, the first rotor would rotate one position. The other two rotors would remain stationary until the first rotor had rotated 26 times (the number of letters in the alphabet and therefore, one full rotation). Then the second rotor would rotate one position. After the second rotor had rotated 26 times (26X26 letters, since the first rotor has to rotate 26 times for every time the second rotor rotates), the third rotor would rotate one position. The cycle would continue like this for the entire length of the message. The result was a shifting shift. In other words, an s could be encoded as a b in the first part of the message, and then as an m later in the message. This principle of the shifting rotors allowed for 26X26X26 = 17576 possible positions of the rotors.
In order for the recipient to decode the message, they would need to know the initial settings of the rotors, and then put the cipher text through the machine to find the plain text. The Germans devised a system by which all of the recipients would set their rotors to predetermined settings according to the date. Each clerk had a book detailing the settings for each day.

Although (I believe) a true Feistel involves splitting into two halves (which doesn't happen here) and where one old half == other new half after a round of encryption, could this algorithm be classified as a Feistel network?

Enigma is not a Feistel cipher. A "Feistel cipher" is a block cipher with a specific structure, namely the whole business with the two halves, the combination of one half with a (one-way) function of the other half and a reversible operation (e.g. XOR), and the swap. See the Wikipedia page which has nice schematics.

So considering Enigma as a kind of Feistel cipher is like considering a salmon as a kind of chicken: yeah, it has no beak, no feathers, no legs and no wings, but could it be a called a chicken ? Strangely enough, I tend to answer no to that. Even though both the salmon and the chicken are edible. But being edible is not sufficient to grant chickenness. Similarly, being a symmetric cipher is not sufficient to grant Feistelness.


Idea for user/pass hashing to prevent rainbow tables, would it work? I'm very new to cryptography (and security in general, for that matter), but I had an idea that I'm sure is very flawed, but is worth asking. If a computer user, online account, etc, needs to verify a username and password, wouldn't this work well?

Upon signup, ask for username and password as usual
Hash username (charliebucket)
Hash username, colon, password (charliebucket:NgWB9pLx), using username hash as salt for user:pass hash.
Upon login, hash username and user:pass
Check if user:pass hash is the same, using hash of username as salt
If user:pass hash succeeds, log in.

In my theory, this would prevent rainbow tables two-fold. If you require 8-character and up usernames and passwords, the pre-hash string will be at least 17 characters, making it unlikely that it would be on a rainbow table. But even if it were, it would take 3+ quadrillion years on a desktop PC, I'd assume it would take a good thousand on a million-dollar cluster.

As I said, I'm fairly new, and don't fully understand anything related to cryptography or hashing (besides "password go in, hash come out"), but I thought there might be a circumstance where this could be used.

The goal for salts is that they be unique to each account and that they be values highly unlikely to appear in a rainbow table. Here, if usernames are unique then so are the salts. Since hash values are long and random, they won't be in rainbow tables. So hashing the username looks like it provides a good salt value to the extent that usernames are unique in your system.

If you're storing password hashes, you should probably be using bcrypt to do so. Bcrypt is a hashing scheme, but it's more flexible and is designed to mitigate more of the typical password attacks than just rainbow tables. For example, your scheme defeats rainbow tables but it doesn't prevent a brute-force attack where the target's username is known, whereas bcrypt also takes that attack into consideration.

So you have a good salt and your scheme will thwart rainbow table attacks. But good password verification schemes should strive for more.

As a non-cryptographic aside, for flexibility I would recommend not hard-coding the salt derivation in the scheme, regardless of what hashing scheme you choose. Derive the salt in the beginning and then store it separately in the database. This way the salt can be updated or changed if necessary. (Also, no one has to go look at code to figure out how it's generated.) If you choose not to store the salt in the database, then you can never change an account's salt should the need arise and you also have to have to update the password hash if the username ever changes.


Can a file encrypted with one tool be decrypted with different tool? I'm new to cryptography and I'm trying implement a file encryption feature into a Python program but I'm running into a big issue...what is needed for someone else to decrypt the file?! Obviously, I can decrypt the file on my end. I'm not worried about that.

Basically, I need to encrypt a file and send it to another person who then needs to be able to decrypt the file using their system. I thought the other person would just need to know the form of encryption used (AES, RSA, etc) and the respective key to decrypt the file. But I guess that's not the case.

So, what is required to get this scenario to work? I know I'm not the first person to want to send an encrypted file to someone else and have them decrypt it.

This is what I need to know:

Can a file encrypted using Python be decrypted using, say...C# or another programming language?
Exactly what information about the encryption process is required for the person receiving the encrypted file to successfully decrypt the file?

Your help will be greatly appreciated. I don't know what I'd do without a community like this.

As mentioned in the comments what the receiver needs to know is effectively: Formats, Algorithms and Keys.

Now this may be a bit of an unsatisfying answer to most people, so I'll go into more detail.

Formats

The sender and the receiver have to agree on a format on how to actually read the data and how to interpret it. If I give anyone a chunk of Word document data without any format specification he will have a really hard time figuring out what field means what. So in your scenario you have to think of some specification on how to transmit your files, this may be as simple as the following, but must be done in order to ensure compatibility.

Example: RSA encrypted file

Offset        | Size | Type | Name |Description
0             | 4    | bytes| Magic| A constant magic value to identify this packet
4             | 4    | bytes| Ver  | A little-endian (LE) 32-bit integer denoting the format's version
68            | 64   | bytes| Cert | A SHA-512 hash of the certificate used to encrypt the key
72            | 4    | int  | KeyLe| A LE 4-byte integer holding the size of the ciphertext
76            | 8    | int  | Size | Size of the actual encrypted data
84            | 12   | byte | Nonce| A random nonce used for GCM
96            | KeyLe| int  | KEM  | An encrypted random number
96+KeyLe      | Size | byte | Data | The encrypted file
96+KeyLe+Size | 16   | byte | Tag  | The GCM tag on the data

So far for the format, now for the

Algorithms

Only knowing how to read in the data doesn't help you alot. You also need to know how to interpret it. This is where the algorithms come into play. For the above example you need to know that f.ex. Header Version 1 would be to use AES-256-GCM to encrypt the data using the nonce and outputting / verifying the appended tag along with authenticating the header as associated data (AD). Furthermore you'd have to know that this version requires you to use HKDF (salt=empty, no additional info) to derive the key from the RSA decryption of the Key value using the certificate with the hash matching the Cert entry. You'd also need to know that you select a key by randomly choosing a number smaller than the RSA modulus and by encrypting this number with RSA (=Key) and using the HKDF of the secret integer as the AES key.

Keys

The keys aren't all that interesting at this point. You'd need to somehow trust the authenticity of the public key (using certificates?). But that's basically it with key management with this example. Of course you also have to consider things like key revocation, key expiration and key erasure but those are different problems...

To finally answer your first question whether the programming language matters. It doesn't if both systems use the same Formats, Algorithms and the right keys, because you wouldn't be able to distinguish the results of a C# from a Python from a C++ implementation then.


Paillier equality test under the same key I have a similar question to this one:
Is an equality test possible when using paillier crypto?

However I want to do the following:

Given the Paillier Cryptosystem.
Given the function $f(input)$, which both Alice and Bob have.
$f()$ is a deterministic function.
Both Alice and Bob have the input of this function.

Alice encrypts a message $m=f(input)$ with Alice's public key and publishes $enc(m)$.

Is it know possible for Bob to verify, knowing $m=f(input)$, if $dec(enc(m))=m$, but without knowing Alice's private key?

If you intend to make $f$ public, or that $f$ does not depend on the secret key, that's not going to work:

The Paillier cryptosystem is proven to be IND-CPA under the decisional composite residuosity assumption.
If a function $f$ exists, like you describe in the question, this function would immediately break IND-CPA
By contraposition, function $f$ does not exist (under the assumption that the cryptosystem is IND-CPA).

However, if $f$ is actually the decryption function with the private key hard coded or any modification of this, it would work. However, that means Bob might be able to extract the private key from $f$. If you want that to be computationally hard, you will need to prove this property.

That last part is quite difficult and maybe even impossible. I am not aware of a property like that for the Paillier cryptosystem. Composite moduli do have some properties which might be suitable. For example computing an $e$-th root of a fixed public element is computationally hard but knowing this root does not reveal the factorization of the modulus. But I don't know how you could adapt this in the Paillier cryptosystem.


Changing SHA-1 constants an functions: Does it affect security? I have been looking into the SHA-1 algorithm. I found that there are a set of functions and constants in the algorithm that have been standardized (section 5 of RFC 3174). If I want to use SHA-1, which I know is not advisable, does changing the constants and altering the functions have a positive effect on the security of the algorithm, assuming the attacker does not now of this alteration?

I wouldn't suggest heuristically changing constants. However, there is a method with rigorous foundations that considered using randomized hashing in digital signatures. This method has the advantage that one can assume less from the hash function, and thus if the hash function is not "fully" collision resistant, the signature scheme can still be secure. In the method described in Strengthening Digital Signatures via Randomized Hashing by Halevi and Krawczyk, one only needs target collision resistance, which is much weaker than full collision resistance. Of course, this only helps in the context of signatures.


c# Correct Triple Des Block Encryption Usage I found the below code online, but in its original state, the encryption was not using any padding (Padding.None), and was encrypting in blocks of 8. I wasn't able to get this code to properly encrypt / decrypt data so I was forced to have it encrypt the full length of the text. Is there something fundamentally wrong with what I have done? If so, could someone please show me the proper way to encrypt text in blocks of 8?

// 168-bit (three-key) 3DES (Triple-DES) encrypt a single 8-byte block (ECB mode)
// plain-text should be 8-bytes, key should be 24 bytes.
public byte[] TripleDesEncryptOneBlock(byte[] plainText, byte[] key)
{
    // Create a new 3DES key.
    TripleDESCryptoServiceProvider des = new TripleDESCryptoServiceProvider();
    // Set the KeySize = 192 for 168-bit DES encryption.
    // The msb of each byte is a parity bit, so the key length is actually 168 bits.
    des.KeySize = 192;
    des.Key = key;
    des.Mode = CipherMode.ECB;
    des.Padding = PaddingMode.None;
    ICryptoTransform ic = des.CreateEncryptor();
    byte[] enc = ic.TransformFinalBlock(plainText, 0, 8);
    return enc;
}
public byte[] TripleDesDecryptBlock(byte[] plainText, byte[] key)
{
    // Create a new 3DES key.
    TripleDESCryptoServiceProvider des = new TripleDESCryptoServiceProvider();
    // Set the KeySize = 192 for 168-bit DES encryption.
    // The msb of each byte is a parity bit, so the key length is actually 168 bits.
    des.KeySize = 192;
    des.Key = key;
    des.Mode = CipherMode.ECB;
    des.Padding = PaddingMode.None;
    ICryptoTransform ic = des.CreateDecryptor();
    byte[] dec = ic.TransformFinalBlock(plainText, 0, 8);
    return dec;
}
// Encrypt Text
textBox5.Text = ByteToString(TripleDesEncryptOneBlock(StringToByte(textBox5.Text),
    StringToByte("1 2 3 4 5 6 7 8 9 1 1 2 ")));
// Decrypt Text
textBox5.Text = ByteToString(TripleDesDecryptBlock(StringToByte(textBox5.Text),
    StringToByte("1 2 3 4 5 6 7 8 9 1 1 2 ")));

My Related question on stack overflow

3DES is a block cipher which processes "blocks" of 64 bits. A block cipher is not sufficient to encrypt a message, defined as a sequence of potentially many bytes. Hence the use of a mode of operation which organizes things; this may imply some padding, and an Initialization Vector.

TripleDESCryptoServiceProvider can do all that: you specify the key, the chaining mode, the padding and the IV, and then you call CreateEncryptor() (or CreateDecryptor()) which returns an ICryptoTransform instance, on which you call TransformBlock() and TransformFinalBlock() to process all your data. You can process the data by chunks (you call TransformBlock() several times, and finally TransformFinalBlock() once).

The code you show is trying to do the opposite of what you seek: it uses TripleDESCryptoServiceProvider to process a single block, without any chaining or padding (hence the use of ECB and no padding).

Note that:

ECB is known to be a weak chaining mode (it leaks quite a lot of information on typical input data).
Secure modes of operation (e.g. CBC) need an appropriate IV: in the case of CBC, it must be chosen randomly and uniformly with a cryptographically strong random generator, and it must never be reused (the point of the IV is that you can reuse the same key for several messages, as long as each message has its own IV). The IV is normally transmitted along with the encrypted message (in the clear), since the decryptor will need it.
Ciphers process bytes. A "string" is a sequence of characters, thus a conversion step is needed. I assume that your StringToByte() method (which you do not show) does that. Beware of charsets: you want the conversion to always operate the same way, regardless of how the local machine was configured.


Does the generator size matter in Diffie-Hellman? For the Diffie-Hellman protocol I've heard that the generator 3 is as safe as any other generator. Yet, 32-bit or 256-bit exponents are sometimes used as generators.  What is the benefit of using these very large generators if they are just as safe as the generator 3?

If 3 is not the safest generator, how could one calculate the shortest length generator that would be considered secure?

The security of Diffie-Hellman depends upon the group in which DH is used, but not upon which generator is used for this group. See note 3.53 (chapter 3, page 103) of the Handbook of Applied Cryptography.

In more details: for DH, we use a subgroup of size $q$ of the integers modulo $p$ (a big prime) with the multiplication as group operation. $q$ should be a prime of length at least $2n$ bits for a $2^n$ security level (or, at least, $q$ should have a prime divisor of at least $2n$ bits). Typical parameter sizes are 160 bits for $q$ and 1024 bits for $p$, or 256 bits for $q$ and 2048 bits for $p$. The generator $g$ is an element of order $q$.

When $p$ is a "safe prime", this means that $\frac{(p-1)}{2}$ is also prime. We then define $q = \frac{(p-1)}{2}$. In that situation, the order of any non-zero $g \bmod p$ (except 1 and $p-1$) is either $q$ or $2q$, hence every $g$ between $2$ and $p-2$ (inclusive) is a fine DH generator and ensures optimal security. Therefore it is customary to select a $g$ which makes computations easier, usually $g = 2$ or $g = 3$.

Another way to define a DH group is inherited from what is done with DSS (a signature algorithm which also works in that kind of group): we first select a prime $q$ of appropriate size (e.g. 160 bits), then we look for $p$ by setting $p = qr+1$ for random values of $r$ of the right size (so that $p$ has the size we need), until we hit a prime $p$. This allows the use of a smaller $q$, thus smaller DH exponents and faster computations; on the other hand, we cannot choose the generator as freely in that case, because there are only $q-1$ generators of a subgroup of order $q$ modulo $p$. So we take a random value $s$ and compute $g = s^{(p-1)/q} \bmod p$. This yields an appropriate generator, but not a small one such as $2$ or $3$.

Why wouldn't everyone use the obvious $2$ or $3$ rather than 256-bit numbers?

A modular exponentiation uses a "square and multiply" algorithm. Using $2$ as generator simplifies the multiplies, but not the squarings, which represent the wide majority of the computation (especially when using window-based optimizations). Using $g=2$ is neat but does not imply that much of a performance enhancement.

Window-based optimization groups multiplications. Basically, you precompute $g^2, g^3 \dots g^{15}$; then, you do the squarings and you multiply with one of the precomputed values only once every four squarings. This is with a 4-bit window, you can have bigger windows; there are possible savings on the window building too. This is why the squarings use more than $\frac{2}{3}$ of the total CPU cost, closer to 80 or 85%. This leaves relatively little to optimize with $g=2$.

Most probably, someone had at some point a fuzzy feeling of a 256-bit number being "more secure" in some unspecified way. I have not seen that personally. Several protocols (e.g. IKE, used for IPsec) use the "Oakley groups" from RFC 2412 (Appendix E) which have $g=2$.


What is the procedure to proceed towards breaking a cipher text when the process of encryption is not known? I mean , if one is provided with a cipher text and the process of encryption through which text has has been encrypted has not been provided , then how is the cipher text broken ? Is frequency analysis the first step towards checking the alphabet's frequency and is there any standard procedure towards breaking cipher text ?

Let's assume that I encrypted my text using a trigonometric function , but that is not known by the cryptanalyst who is trying to break the code , so what process would be traditionally deployed for breaking the cipher text ?

Cryptanalysis is not a standardised process with recipes to decrypt encoded messages...it has a lot to do with circumstances such as the amount (length) of ciphertext available, in what context it was retrieved (is it likely to be part of an authentication protocol, or human communication) and so forth. It often involves creativity, and lots of trial-error and patience since it is obviously a task that is difficult by design.

If there is absolutely no context information, the analyst has little choices but to closely examine the ciphertext for any kind of patterns/structure, and identify anomalies to work on. This could include things like

Frequency of characters
Appearances of combinations (which might originate from the same plaintext words)
Ciphertext structure (especially if several messages have been received): do there appear to be checksums, is the length fixed,
etc.

Note that the above is by no means exhaustive nor very helpful for solid encryption schemes. It is just to address your question and point out why it can not be answered - there simply is no standard procedure.

More importantly, most encryption nowadays does not rely on secrecy of the algorithm. Cryptographic schemes can and should be publicly known, so that the public can point out and correct potential weaknesses, which increases resource asymmetry between the "defenders" (developers) and adversaries, and thus makes attacks less likely. This ultimately leads to more public trust and acceptance of the method.

So it is no problem at all when a cryptanalyst knows that you used RSA etc. to encrypt your message, it is still infeasible to "break" the ciphertext, as you put it.


Discrete Logarithm Notation Im studying for my final, and some of the practice problems that I have found have discrete logarithms in this notation $L_n(p)$.

What does this notation equate to?

For example:

$\log_n(x)$ means the base-$n$ logarithm of $x$. It returns a value $y$ such that $n ^ y = x$.

Since you're working with discrete logarithms, the base will probably be the generator $g$ for your group.

edit

$L_{13}(x)$ appears to be a shorthand way of writing the above. The only way to find out otherwise would be to consult the notation definitions from the paper (or author) if possible, because it could mean something else entirely or something more specific.


What is the difference between CSPRNG and PRNG? What is the difference between CSPRNG and PRNG?

Is there performance differential between them? For example: We use PRNG for key generation which is very expensive and CSPRNG for IV/nonce in block ciphers which is fast?

What is the difference between the two types of RNGs?

"PRNG" means "Pseudorandom Number Generator" which means that a sequence of numbers (bits, bytes...) is produced from an algorithm which looks random, but is in fact deterministic (the sequence is generated from some unknown internal state), hence pseudorandom.

Such pseudorandomness can be cryptographically secure, or not. It is cryptographically secure if nobody can reliably distinguish the output from true randomness, even if the PRNG algorithm is perfectly known (but not its internal state). A non-cryptographically secure PRNG would fool basic statistical tests but can be distinguished from true randomness by an intelligent attacker.

For instance, consider the following generator:

There is an internal state s which is a sequence of 20 bytes.
The generator produces a long sequence of bytes by 20-byte chunks.
To produce the next chunk, the algorithm is: output s, then set s to SHA-1(s).

This PRNG will be very good statistically, but it is trivial to distinguish from true randomness: just take two consecutive 20-byte chunks in the output, and see if the second is the result of SHA-1 over the first. This is not a cryptographically secure PRNG.

Of course, every CSPRNG is a PRNG, but not every PRNG is a CSPRNG. Some non-CS PRNG like the Mersenne twister can achieve quite high a performance and be adequate in non-cryptographic situations where there is no intelligent attacker to defeat (e.g. physics simulations). Although there also are some known high-performance CSPRNG (e.g. these stream ciphers), a non-CS PRNG may give an edge in contexts where the lack of cryptographic security is not an issue.


Is this commutative encryption protocol secure? My assumptions are:

encryption must be commutative
man-in-the-middle is not an issue

I would like to implement the following scheme between 2 parties ($A$ and $B$) to exchange a key:

Lets $C = P \oplus F(K, IV)$ is a commutative encryption, resp. CTR mode of some symmetric block cipher with random key $K$, random initialisation vector $IV$, and $P$ is plaintext, $C$ ciphertext.

$A$ has a $P$ which would like to share with $B$

So the following protocol would be done:

$A$ will choose a random $K_1$ and $IV_1$ and produce $C_1 = P \oplus F(K_1, IV_1)$
$A$ will send $C_1$ to $B$
$B$ will choose a random $K_2$ and $IV_2$ and produce $C_2 = C_1 \oplus F(K_2, IV_2) = P \oplus F(K_1, IV_1) \oplus F(K_2, IV_2)$
$B$ will send $C_2$ to $A$
$A$ will decrypt $C_2$ using $K_1$ and $IV_1$ so produce $C_3 = C_2 \oplus F(K_1, IV_1) = P \oplus F(K_1, IV_1) \oplus F(K_2, IV_2) \oplus F(K_1, IV_1) = P \oplus F(K_2, IV_2)$
$A$ will send $C_3$ to $B$
$B$ will decrypt $C_3$ using $K_2$ and $IV_2$ so produce $P = C_3 \oplus F(K_2, IV_2) = P \oplus F(K_2, IV_2) \oplus F(K_2, IV_2)$
$A$ and $B$ shares the same value $P$ now

Is there any security risk by combining any of the $C_1$, $C_2$, $C_3$ to get the actual value of $P$?

$C_1 \oplus C_2 = F(K_2, IV_2)$

$C_1 \oplus C_3 = F(K_1, IV_1) \oplus F(K_2, IV_2)$

$C_2 \oplus C_3 = F(K_1, IV_1)$

Could it be any possible attack how to get the value $P$?

Yes it is possible for a passive eavesdropper to recover the secret $P$.

Here's how:

The attacker observes $C_1,C_2,C_3$ and formes the XOR of all those values. That's it, the result of $C_1\oplus C_2 \oplus C_3=P\oplus F(K_1,IV_1)\oplus P \oplus F(K_1,IV_1) \oplus F(K_2,IV_2) \oplus P \oplus F(K_2,IV_2)=P$ yields the desired plaintext.


Will the complement of a 64-bit key and message produce the complement ciphertext if ECB is used in DES? Say I have a 64-bit message/key:

P1: 1011.......
K1: 0101.......

I run this message/key pair through DES in ECB mode and obtain some cipher that looks like the following:

C1: 1001.......

Now I take a new message/key pair that is the bitwise complement of the first and put it through the same algorithm:

P2: 0100..........
K2: 1010..........

Will it produce the complement ciphertext?

C2: 0110..........

I'm assuming it will due to ECB's deterministic property, but can anyone verify?

In short, yes.

The complementation property of DES states that if $DES_K(P) = C$, then $DES_{\overline{K}}(\overline{P}) = \overline{C}$,  where $\overline{X}$ is the complement of a string $X$.

ECB with DES takes a message $M_1M_2\cdots M_\ell$ and computes $C_1C_2\cdots C_\ell$, where $C_i = DES_K(M_i)$, for $1\le i\le\ell$. Therefore, if you encrypt $\overline{M_1M_2\cdots M_\ell}$ with ECB and DES under $\overline{K}$, then you get $C_1'C_2'\cdots C_\ell'$, where $C_i' = DES_{\overline{K}}(\overline{M_i})$. By the complementation property we know that $C_i' = \overline{C_i}$, so the result is the complement of the ciphertext.


Implicit authentication aritcle First, I want to know what is the logarithm used in the following system of equations (from the paper Flexible and Robust Privacy-Preserving Implicit
Authentication - Domingo-Ferrer, Wu, Blanco-Justicia):

Second I want to understand how one can obtain integer values $r^\prime_1, r^\prime_2, ..., r^\prime_s$ after using logarithm.
Note: All the other values ($R^\prime,r^\prime_0, a_i;\forall i$) in the system are integers.

There are serious errors in the fragment quoted in the question, which is (an appendix of) the paper: Josep Domingo-Ferrer, Qianhong Wu, Alberto Blanco-Justicia, Flexible and Robust Privacy-Preserving Implicit Authentication (in ICT Systems Security and Privacy Protection, Volume 455 of the series IFIP Advances in Information and Communication Technology pp 18-34; also in arXiv:1503.00454).

We are invited to use the technique in [7]: James Demmel and Plamen Koev, The Accurate and Efficient Solution of a Totally Positive Generalized Vandermonde Linear System, in SIAM J. Matrix Anal. Appl. 27 (2005). But in that reference [7] the unknowns $a_i$ are real variables, and the critical issue is numerical stability; when the unknowns in the context are integers, and the system of equations to solve is $\bmod n$ (or at least modular). I'm thus inclined to believe reference [7] can't be directly applied. That might have to do with why reference [7] was not used; quoting section 6 of the paper

  we used straightforward Gaussian elimination which takes
  time $O(s^3)$, although, as mentioned above, specific methods like [7] exist for generalized Vandermonde matrices that can run in $O(s^3)$ (such specific methods could be leveraged in case of smartphones with low computational power).

Even with Gaussian elimination, I am left puzzled at the description of how the authors proceed in the setup phase. My best guess is that their $\log$ really is discrete logarithm to base $g$ in the multiplicative group $\bmod n^2$ (where $g$ is some generator, possibly the same as in the public key); but in that case, the linear system obtained won't be $\bmod n$ as written: an appropriate modulus $m$ would be one with $g^m\equiv1\pmod{n^2}$, and there is no reason that $g^n\equiv1\pmod{n^2}$. I'm cautiously optimistic that using $m=\lambda(n^2)=p\cdot q\cdot\operatorname{lcm}(p-1,q-1)$ would be a step towards reason (note: $\lambda$ is the Carmichael function).

But I see another issue: computing discrete logarithm to base $g$ is computationally involved in the general case even with factorization of $n$ known, we have not been told in appendix B to choose $p$ and $q$ making that operation easier, thus I do not see how we could (as told in section 4.1, Set-up item 4)

  randomly choose $R'\in\mathbb Z_{n^2}$. Find $r'_0,\dots,r'_s\in\mathbb Z_{n^2}$ such..

as to match the system of equations in the question, by the reduction to a linear problem that (my reinterpretation of) the paper suggests.

My best idea to reach the goal of Set-up item 4 is to assume that we can write $R'=g^u\bmod n^2$ and $r'_i=g^{v_i}\bmod n^2$ for $0\le i\le s$, and choose random $u$ and $v_0$ (yielding random-enough $R'$ and ${r'_0}$ with known logarithm). Having done this, $\log(R'/r_0)$ becomes the chosen $u-v_0$, $\log(r_i)$ is the unknown $v_i$ for $1\le i\le s$, and indeed if we can solve the linear system of $s$ equations $\bmod\lambda(n^2)$ with $s$ unknowns $v_i$ for $1\le i\le s$, then that solution yields what's wanted in Set-up item 4.

I find the paper lacking on many more points than exposed above; among such pitfalls:

No argument is given that what's disclosed at Set-up item 5 does not allow factoring $n$ or finding information about the user's profile, which is essential to the stated goal; the closest thing being an assertion without proof (made quite moot by what I emphasized)

  If both parties are honest, then the carrier learns $|X\cap Y|$ but obtains no information about the elements in $X$ or $Y$.

There are striking similarities with earlier work blinding set operations (including counting the intersection) using the Paillier cryptosystem; at least the seminal reference [9] (Michael J. Freedman, Kobbi Nissim, Benny Pinkas, Efficient private matching and set intersection, in proceedings of Eurocrypt 2004) is in the bibliography, but the text makes no reference to it.
We are given benchmarks of the setup phase, but no way to reproduce or analyze these, and not even a clear description (hence the question);
The performance numbers are given for a CPU only specified as "Intel i7", which leaves performance unspecified by a wide factor, given the variety of processors sold under this label;
In appendix B, the decryption for the Paillier cryptosystem has a number of small issues, and two serious ones:

the final formula uses the wrong modulus $n^2$, rather than $n$;
it is missing the critical Euclidian division by $n$ step!


Constant data as input to hash I want to use hash function on some data, and part of this data, might be constant for a certain period. The output of the hash function is used as authentication data (MAC).

I want to know if there is:

Reason to use/not use this data as input to the hash? (In the context of authenticity of data…)
Impact on the "strength" of the hash function – can this constant help attacker to find out the source data of the hash function? (Help him do some smart brute force or something.)

If you need a MAC, use a MAC. For example, HMAC which uses a hash function. Don't try to use a random hash function in your own scheme, because some such schemes are not secure.

  Reason to use/not use this data as input to the hash? (In the context of authenticity of data…)

If you do have a secure MAC, any constant data will not affect the authenticity. Two different inputs will have completely different and unforgeable MACs even if they are known to differ in only e.g. one bit.

  Impact on the "strength" of the hash function – can this constant help attacker to find out the source data of the hash function? (Help him do some smart brute force or something.)

Known constant data will not make it any weaker than if the data was not there. In the case of a hash function (not MAC) it could slightly improve a brute force search of two hashes if you knew they shared a long enough prefix... but as long as the data is unpredictable enough that shouldn't matter, and in the case of keyed MACs there is no such advantage.


Is ChaCha20 safer than AES with respect to side-channel attacks? I've already seen some topics on this matter, but I feel like my question hasn't really been answered.

Given the following:

AES must be implemented in hardware (i.e. using the AES-NI instruction set) to ensure the best protection against side-channel attacks that target the algorithm's implementation (because of MixColumns operations)
Other encryption algorithms such as the Salsa20 family and NORX are less prone to such issues (if well implemented, at least in software)

...can we say that it is safer$^1$ to use such algorithms instead of AES if one may not ensure that AES-NI is properly implemented in the hardware that's being used ?

For instance, if one uses some x86-64 CPU that features this instruction set but whose design is kept secret, can AES be considered safe ? Respectively, are the other algorithms safe(r) on such a platform ?

$^1$Note that NORX is still in its early stages and has yet to win the CEASAR competition as well as withstanding the test of time, so it is only safe "on paper" for now

It basically depends on what you consider side-channel attacks.

If you consider time/cache side channel attacks than chacha20 has been design with resistance to such attacks in mind while AES didn't.
In fact, AES is vulnerable to these kind of attacks (as they were invented after AES was designed). But, hardware implementations, such as AES-NI are protected because they don't use caches and execute in constant time.

If you consider also power/electromagnetic side-channels then both algorithms are vulnerable and in this sense the community has researched A LOT more on protections for AES then for Chacha20 which will be significantly harder to protected due to its ARX nature which require expensive masking conversions.
So it will be more easy to find protected , pure sw, AES implementations, even in open source. But you need a protected implementation, otherwise you will be vulnerable.

To summarize you have to check which side-channel attacks you want to protect against and the security claims of your implementation. It can't be simplified as "AES needs to use AES-NI" because we can have side-channel protected AES in pure software (see the link above).


A number theory problem in RSA Let say we have $N=pq$ (Both $p$ and $q$ are safe primes, meaning $\gcd(p-1,q-1)=2$)

let's assume $e$ is an odd number which can be efficiently factored and assume that we know the $e$'th root of 1 modulo $N$ - call it $r$ - as well es $e$ and its prime-factorization. There is a claim that knowing the $e$'th root of 1 modulo $N$ we can find such $y>1$ and an odd prime $p_0$ such that $y^{p_0} = 1 \bmod N$.

How can we calculate $y$ and $p_0$?

If we know $e$, then it's easy.

If don't have to know the factors, but it does make it easier - as fgrieu pointed out, either $(p-1)/2$ or $(q-1)/2$ will appear as one of the prime factors, that will allow us to immediately recover $p, q$

Once we have that, then we know that we want:

$$y^{p_0} \equiv 1 \pmod p$$
$$y^{p_0} \equiv 1 \pmod q$$

If we have $y \equiv 4 \pmod p$ (or any other quadratic residue) and $p_0 = (p-1)/2$ (which is prime), then we satisfy the first equation.

If we have $y \equiv 1 \pmod q$, then we satisfy the second equation.

It's easy to find a $y$ that meets both modulii (as $p, q$ are relatively prime) using the Chinese Remainder Theorem, and so that's our answer.


Create a time capsule using a Word processor I was wondering if there's any option to create sort of a time capsule in a Word document, i.e. not encrypted by password rather than a date. Let's say I send the document today but the receiving side can open the document only the next month on a specific date.

I know no feature like this built into any word processor. And, despite work on so-called time-capsule cryptography, we know no practical[*] way to implement one without relying on trusted hardware or trusted third party.

To achieve this, we can use the help of a trusted third party/server. It can generate and publish public keys for which it will publicly release the private keys at a set date. The sender enciphers the message with the public key selected per the desired release date. The receiver can't decipher until that date. To do so, s/he must get online, get the private key (now published) from the third party, then decipher.

[*] Problems with proposed time-capsule cryptography systems requiring no trusted external hardware/party are that their delay of release is too imprecise, and they would be prohibitively costly. They achieve timed release by requiring sequential iteration of a certain computation, assumed to require at least a certain time $T_0$. To obtain a delay $T$, the receiver is forced to perform $t=T/T_0$ operations, at full rate, during the whole timed release. But $T_0$ varies a lot with the technology, and the fasted high-speed logic is prohibitively expensive. That used to be GaAs, now perhaps InP, or is it unobtainium-on-diaphire immersed is liquid nitronium.


Why use argon2i or argon2d if argon2id exists? So I am currently working on a GitHub project of mine and I want to implement Argon2. The problem is that I dont really know a lot about it. Internet research is not really helpful, because Argon2 is only 2 years old so all that really exists are scientific papers and that GitHub page.

But before I carry on developing with argon2 I need some important question answered. I will start with the first one :

If Argon2id is the hybrid version of Argon2i and d then why do people even use one of the other two, would it not be more secure to use something that is resistant to side channel attacks and gpu cracking?

The current Argon2 draft RFC, I think, provides a good, reasonably brief answers to this question.  TL;DR: most people will indeed want to use Argon2id and not the "pure" variants.

The introduction summarizes the issues quite well:

  Argon2 has one primary variant: Argon2id, and two supplementary variants: Argon2d and Argon2i.  Argon2d uses data-depending memory access, which makes it suitable for cryptocurrencies and proof-of-work applications with no threats from side-channel timing attacks.  Argon2i uses data-independent memory access, which is preferred for password hashing and password-based key derivation.  Argon2id works as Argon2i for the first half of the first iteration over the memory, and as Argon2d for the rest, thus providing both side-channel attack protection and brute-force cost savings due to time-memory tradeoffs. Argon2i makes more passes over the memory to protect from tradeoff attacks.

Basically, there are two kinds of attack considered:

Side-channel timing attacks.
Time-memory tradeoff (TMTO) attacks.

Argon2d is vulnerable to timing attacks, but offers the best resistance to TMTO (section 9.2):

  The best tradeoff attack on $t$-pass Argon2d is the ranking tradeoff   attack, which reduces the time-area product by the factor of 1.33.

Argon2i is invulnerable to side-channel timing attacks, but is weaker against TMTO:

  The best attacks on the 1-pass and 2-pass Argon2i is the low-storage   attack described in [CBS16], which reduces the time-area product (using the peak memory value) by the factor of 5.  The best attack on 3-pass and more Argon2i is [AB16] with reduction factor being a function of memory size and the number of passes.  For 1 GiB of memory: 3 for 3 passes, 2.5 for 4 passes, 2 for 6 passes.  The reduction factor grows by about 0.5 with every doubling the memory size.  To completely prevent time-space tradeoffs from [AB16], number $t$ of passes must exceed binary logarithm of memory minus 26.

Argon2id sits in between:

  The best tradeoff attack on 1-pass Argon2id is the combined low-storage attack (for the first half of the memory) and the ranking attack (for the second half), which bring together the factor of about 2.1.

Since the Argon2 runtime grows linearly with the number of passes, Argon2i with six passes is about six times as slow as Argon2id with one pass.

The draft RFC also states (without explanation) that Argon2id resists timing attacks, and recommends it as the primary variant, and explicitly telling you (section 4, "Parameter choice") that if you don't know which to use, you should pick Argon2id.  You should probably wait until the RFC is approved to fully commit to anything, but in the meantime if you're writing some early code it makes sense to bias things in favor of Argon2id.


Are two outputs of a PRF computationally indistinguishable when the keys are somehow related? This question is related to my previous question “Are two outputs of a PRF computationally indistinguishable when using two different keys??”, but in this question the keys are related.

Assume $c_i$ is a counter: $c_i \in \{0,1,..., n\}$. Also, let $k$ and $k'$ be  two independent keys.
Let $f(.)$ be a pseudorandom function. Let $x$ be an input (or fix value).

When $c_i=0$  : $\ z_i=f(k,x)$
When  $c_i \in \{1,2,... n\}$: $\ z'_i=f(k+k'_i,x)$, where $k'_i=f(k',c_i)$.

Question: Are $ z_i$ and  $z'_i$ computationally indistinguishable?

They are indistinguishable because the keys are related only by a value that random from the distinguisher's point of view. More formally, you can argue that your distribution is indistinguishable from one in which all PRF keys are chosen independently. Note that this is very sensitive to the fact that the distinguisher can't query $f(k',\cdot)$.
What you described is this distribution induced by the following process (I will rename $k$ to $k_0$). It is easier to assume that the $x_i$'s are just some arbitrarily fixed values. Even if they are chosen adaptively, it doesn't substantively change the nature of the argument.

Process 0:

$k_0,k' \gets \{0,1\}^\lambda$
for $i \in \{1,\ldots,n\}$: set $k_i = k_0 + f(k',i)$
output $f(k_0, x_0), f(k_1, x_1), \ldots, f(k_n, x_n)$

This process uses $k'$ only as a key to $f$, and nowhere else. The PRF security guarantee is that it has a negligible effect on the output to replace distinct outputs of $f(k',\cdot)$ with randomly chosen values. The resulting process is:

Hybrid process 1:

$k_0 \gets \{0,1\}^\lambda$
for $i \in \{1,\ldots,n\}$: choose $r_i \gets \{0,1\}^\lambda$
for $i \in \{1,\ldots,n\}$: set $k_i = k_0 + r_i$
output $f(k_0, x_0), f(k_1, x_1), \ldots, f(k_n, x_n)$

Observe that this hybrid process uses $r_i$ only as a one-time pad to mask $k_0$ (here I'm assuming "+" refers to a group operation like XOR). Since each $r_i$ is used only once in this way, and nowhere else, it means each $k_i$ is distributed uniformly. So we can simplify (with no effect on the output distribution):

Hybrid process 2:

$k_0 \gets \{0,1\}^\lambda$
for $i \in \{1,\ldots,n\}$: choose $k_i \gets \{0,1\}^\lambda$
output $f(k_0, x_0), f(k_1, x_1), \ldots, f(k_n, x_n)$

Now each $k_i$ is chosen uniformly/independently, and used only as a PRF seed. From here you can apply the PRF security and replace each term $f(k_i, x_i)$ with a random value. Technically speaking you would perform $n+1$ hybrids to do this, one for each $k_i$ to which you are applying the PRF security guarantee. The final result will be a process that outputs $n+1$ uniformly chosen values.
For an exercise, think carefully about what step of the argument goes wrong when the adversary is also able to query $f(k',\cdot)$.


Secure distance calculation I am working on securing a feature in a csv file.  My goal is to encrypt, anonymize, mask.... etc the content of the records of the feature while preserving the distance between the characters. as example :
        record 1 : mtlcfg
        record 2 : mtlfff

The distance between them is 2 so I want to secure the actual values and preserve the distance on the secured value so the other party is able to retrieve the distance without retrieving the actual values.

I know that adding a noise vector  will work and preserve the distance but it is not secure enough.  All papers that I am reading now are focusing on multi-party secure distance computation such as additive homomorphic encryption. Yet this doesn't match with my case, all I want to do is to be able to calculate the distance on secured content. Can anyone suggest any papers to guidance I am really lost in a lot of papers

You asked a How do I question. You probably asked a Should I question. As in "Should I release a data set that reveals the distance between two strings where everything else is anonymized?" The answer is No unless you're making a crossword puzzle. (XKCD beat me to the joke for something similar. Your scenario is much more crossword-like however.)

Even if you found a scheme that didn't directly reveal individual letters, just having the information you get from string edit distances reveals a lot of information. Example: You have two records in a medical trial program with similar demographic data. You suspect "Bob Example Sr." and "Bob Example Jr." participated. Your two similar rows of data have “ “ “anonymized” ” ” (this needs triple scare quotes to triple scare you out of becoming responsible for publicizing poorly anonymized data) name records which are both 15 characters long and differ in one character. Start making guesses.

One could also build a weighted graph of dictionary words. (Where every node is a word and every pair of nodes is connected by an edge with weight equal to their edit distance.) For your idea you are hiding the labels of each node but not the edges or weights. One could make an informed guess at the values of the encrypted data by looking for similar sub-graphs in both the encrypted and dictionary-based graphs. Once you find one answer it becomes easier to guess the rest.

It is very difficult to design a system that anonymizes complex data sets. Otherwise intelligent people think they're outwitting hackers when they do things like hash email address, credit card info, or social security numbers. And that's the most obviously de-anonymizable scheme one can think of.

The most powerful tool to deanonymize data is to exploit the relations between data. If the purpose of your encryption is anonymization while maintaining properties in the original data then you're trying to do two things that are at odds with each other. It's a lot like deliberately encrypting with the same key/nonce pair even if you could find the perfect scheme.

Now to answer the "How do I [best stick a fork in an electrical socket"] part. I can think of three methods.

Store a table that relates pairs of records to their edit distance. This requires $O(n^2)$ space but is the least bad option. Omit the original string data or substitute it with randomly assigned ID numbers. You can't add new data to an annoymized database with this method.
If you want the Hamming distance between two strings, then use one substitution cipher for the first character of each string, another for the second, and so on. Breaking a substitution cipher is easy enough that it requires no knowledge of modern cryptography. (Or much knowledge at all beyond literacy.)
If you want Levenshtein distance then you use only one substitution cipher. This choice is also horribly insecure.

There may be better privacy-preserving methods than 2 and 3, but not 1. There may be way more complicated ways involving "multi-party secure distance computation, oblivious transform such as secure modular hashing, additive homomorphic encryption" but if any scheme leaks the data you say you want to preserve to a person who holds a copy of the supposedly anonymized data then it's no better at preserving privacy than 1.


Does this simple signature scheme work? Let's say my public key is defined as $P = p \cdot G$, where $p$ is my private key and $G$ is a generator point of an elliptic curve. If I wanted to sign a message $m$, could I do the following?

Hash $m$ to a number using a hash function: $h = Hash(m)$.
Compute signature as $S = \frac{p}{h} \cdot G$.

The verification of the signature can then be done by checking that $P = Hash(m) \cdot S$.

This seems like it should work - but also seems too simple - so, I'm wondering if there is anything I'm missing here.

This signature scheme doesn't even provide UF-KOA security.

The attack is simple: When you want to forge a signature for a message $m$, given a public key $P$, simply compute $h=H(m), h'=h^{-1}\bmod q$ and $S=h'\cdot P$, with $q$ being the order of the subgroup generated by $G$ (usually the curve order). $S$ is then your forged signature for $m$.

This works as:

We can efficiently compute the order of a curve.
We can efficiently find modular multiplicative inverses.


Is it possible to change PGP / GPG Key Size on an exisiting key? Is it possible for myself to change the key size (say from 2048 to 4096) on an EXISTING PGP / GPG key, and just republishing that key?

Or do I have to generate a new key all together?

I want to say that you have to create a new key pair, but I don't have enough documentation either way to support a claim.

Thanks for the info Jens Erat

There is no way to "upgrade" an OpenPGP key. You will have to create a new one, and you will loose your reputation in the web of trust.

Think about:

Giving your new key with the old one, so other could follow the signatures
Revoking the old one after some time
Using a seemingly unnecessary large key as primary key and smaller subkeys for day-to-day usage. You will never need the primary key for anything but signing other keys (which is rare) and others verifying your signatures (cheap anyway).

Source


Iterations of pollards kangaroo attack on elliptic curves I want to understand the Pollard kangaroo attack on elliptic curves. I found this Pollard's kangaroo attack on Elliptic Curve Groups Q/A pretty helpful, but not complete. The posts provides a pretty good algorithm for the attack:
def pollardKangaroo(P, Q, a, b, N):
    # Tame Kangaroo Iterations:
    xTame, yTame = 0, b * P
    for i in range(0,N):
        xTame += Hash(yTame)
        yTame += Hash(yTame) * P
    # yTame == (b + xTame) * P should be true
    # Wild Kangaroo Iterations:
    xWild, yWild = 0, Q
    wildLimit = b - a + xTame
    while xWild < wildLimit:
        xWild += Hash(yWild)
        yWild += Hash(yWild) * P
        if yWild == yTame: return b + xTame - xWild
    # No result was found:
    return None

I did the algorithm on paper and it worked. $P$ and $Q$ are the points in the ECDLP: $Q = n\cdot P$. $a$ and $b$ give the interval, in which the attack searches for $n$. So the algorithm can only succeed if $n \in [a,b]$. Now I got two problems: The hash-function and the parameter $N$ are not explained/defined.
My questions:

Is the hash-function just a semi-random generator and can be pretty simple (e.g. H(point) = x + y + 1)?
How exactly is $N$ defined? What value should $N$ be? How does the value of $N$ affect the algorithm?

My First Attempts:
So I did some testings on the curve $E: y^2 = x^3 + x^2 + x$ with $F_{131}$ and the points $P = (42,69)$ and $Q = 42 \cdot P$. My results for different $N$:

My result for a different Hash function:

So this got me confused, because I did not see any results for different N and I thought only the hash-function is for optimization. But the real answer is much more complex. My sources are wikipedia, handbook of elliptic and hyperelliptic curve cryptography and the original paper.
Answers:

Yes, the hash-function is a semi-random number generator. But it is important for the algorithm! The runtime of the algorithm and the failure rate depends on the hash-function. If the result set is to small, the runtime gets pretty bad. If the result set is to big, the failure rate increases. With the handbook I got the result set $\{ 1,2,..., \sqrt{(b-a)}/2 \}$ and it works pretty good.

I found the answer in the origional paper: $N$ defines the failure rate. If $N$ is low, the failure rate is bigger. So that's the reason I did not see significant changes in the plots. Hint: I still have no idea, if I have to store all intermediate results of the tame kangaroo or not. ( I will edit the post, if I find the answer )

New Code:
The handbook is the main source for the code optimizations. This python code is used with SageMath:
hashValue = 0
def Hash(P):
    if P == 0: return 1
    return int(P.xy()[0]) % hashValue +int(P.xy()[1]) % hashValue+ 1

def pollardKangaroo(P, Q, a, b):
    global hashValue
    hashValue = math.ceil(sqrt((b-a))/2)
    # Tame Kangaroo Iterations:
    xTame, yTame = 0, b * P
    for i in range(0,math.ceil(0.7*sqrt(b-a))):
        xTame += Hash(yTame)
        yTame += Hash(yTame) * P
    # yTame == (b + xTame) * P should be true
    # Wild Kangaroo Iterations:
    xWild, yWild = 0, Q
    for i in range(0, math.ceil(2.7*sqrt(b-a) ) ):
        xWild += Hash(yWild)
        yWild += Hash(yWild) * P
        if yWild == yTame: return b + xTame - xWild
    # No result was found:
    return 0

This now always generates a pretty reasonable plot for the wild kangaroo (same curve and basepoint):
Reminder:
There are a lot of improvments of the algorithm. My algorithm is not perfect! My main goal was to understand how the hash-function and the numbers of iterations affect the algorithm. And! I will edit this post, if I will find some more important informations.


Have I understood pedersen commitment correctly? I want to do a one-sided integer commitment scheme. I.e. the whole process must be non-interactive where I at one point first publicly reveal some data and then at a later time reveal the committed integer which then can be verified.

In the pedersen commitment scheme we have six pieces of data $p$, $c$, $g$, $h$, $x$, $r$. $p$ is the prime order of the group. $c$ is simply $g^x·h^r \bmod p$. $g$ and $h$ are generators of $\mathbb Z_{p\mathbb Z}^*$. $x$ is the committed value and $r$ is a random element.

The scheme would then proceed as follows.

We choose a prime $p$ and generators $g$ and $h$. Can this be some fixed elements that are used every time or must we pick new ones for each run? If so, how? $p=2g+1$ would work, but what about $h$?
We pick our committed $x$ and generate a random element $r$ in the group.
We calculate $c$ and publish $p$, $g$, $h$ and $c$.
To reveal, we simply reveal $x$ and $r$, which then can be verified by recalculating $c$.

Would this be a correct implementation or have I misunderstood something?

Yes, $p$, $g$ and $h$ are system parameters. $g$ and $h$ only need to generate large prime subgroups of $\mathbb{F}_p^{*}$, and the equation $p=2g+1$ is not required. (In fact, if I understand what you mean correctly, it does not always suffice as $-1/2$ has the same order as $2$)

It is important that $g$ and $h$ not be related by a known equation of the form $g=h^k$, because in that case the commitment is easily forgeable. One solution is to fix $g$ and $h$ to be small integers, and verify they have large prime order modulo some prime $p$.


Are large polynomials secure for order preserving "hashing"? (newbie question) I've been searching for some time now for an answer to this simple question: if I have a large polynomial that is secret, and I use it to transform a set of integers so as to obtain a new set that preserves the order for each transformation, can the polynomial be deduced by an attacker only from the output?

Notes to take into consideration:

The polynomial is carefully chosen to assure the outputs maintain order
I'm working only with positive integers
An attacker would only be able to see the generated outputs, never the inputs nor the polynomial (of course)
The attacker could have access to large sets of generated outputs

One example of a valid polynomial could be: $$f(x) = 31x^{15}-27x^{14}+13x^{12}-10x^{9}+5x^{7} $$

Can the attacker deduce the polynomial from the output only, even if I make the polynomial much harder? Are polynomials even a possible solution for order-preserving "hashing"?

I assumed an attacker would be able to find out the secret polynomial through some fancy math tricks and algorithms, so I added the following three difficulties:

I'm "pre-transforming" the input before inserting it into the polynomial by adding a large integer $\beta$ to it, so as to skew the input away from small positive integers - this $\beta$ value is unique per polynomial
I'm "post-transforming" the generated outputs by dividing them with a common divisor as large as possible but that still maintains order - I'm doing this to take some information out of the generated outputs (the remainder) of the divisions. The common divisor is calculated the following way: $$commonDivisor = 10^{numDigits(f(1)-f(0))-1}$$
where $numDigits(x)$ outputs the number of digits in the provided number.
I'm also adding a random deviation value $\alpha$ to every output, that is small enough to not make it larger than the next output: $$out_{n-1}+\alpha_{n-1} < out_{n} + \alpha_{n}$$

All these operations together would produce something like the following:

$$f(x+\beta) = \frac{pol(x)+\alpha_x}{10^{numDigits(f(1)-f(0))-1}}$$

Continuing the previous question, would these changes make any real difference to the challenge of finding the polynomial, or are there ways to crack this?

A  not too technical answer would be very much appreciated due to my lack of experience in this field.

The basic method is easily cracked: it is well known how to find a polynomial of degree at most $k$ from $k+1$ (input, output) pairs; that's the polynomial interpolation problem. There are numerous ways to efficiently carry it for high degree and large integers (one such method is to carry it modulo some medium primes, and use the Chinese Remainder Theorem in the end).

"pre-transforming" alone does not help at all against the above.

"post-transforming" and "adding a random deviation" makes recovering the polynomial more difficult. However, some simple attacks remain feasible, depending on adversarial model. In particular, if the adversary can query the function for arbitrarily large input: the degree of the polynomial and the highest degree coefficient of the polynomial divided by commonDivisor are easily found; then the attack can be repeated by subtracting known high coefficients, until finding all coefficients; in this setup, commonDivisor does not help much.

I do not see how to make the idea secure in a cryptographic sense.

Also: It does not seem that the "post-transforming" method proposed is guaranteed to maintain the property that distinct input leads to distinct output.

Addition following comment: if input is not known, that makes attack harder; however

you proposed: lets assume I have transformed all integers from 0 to 1000, and in cryptographic terms that's to be assimilated to a lot of known plaintext;
known plaintext has been a standard assumption for about as long as cryptography matured to a science, for reasons similar to the above;
as the saying goes: attacks only get better; they never get worse.


Is Permutation conjugate problem hard? Let $x$,$y$,$z$ be permutations. Then public key is $z=xyx^{−1}$ and $y$. Is permutation conjugate search problem easy? if yes, how to find $x$ from $z$ and $y$?
Let be a is Alice's secret key as large number,and X,Y,A=XaYX−a is public key.

encryption Bob pick at random number r,s and B=XrYX−r,C=XrAsX−r,and c=H(C)+m, and (B,c) is cipher text send to Alice.

decryption Alice calculate C=XaBX−a. Cause the discrete logarithm problem of permutation groups is weak,so Alice can calculate C from B. Finally Alice get plain text as m=H(C)+c.

I assume permutation dimension of X is 1988 and permutation is represented as array form.X's order have 256-bit integer.

Is this cryptosystem insecure ?

It looks like it can be solved quickly using a branch-and-bound procedure, assuming that the number of elements in the permutation is not excessively large.

(Notation: I'll use capital letters to specify permutations, and lower case letters to specify individual elements of the permutation); in addition, I'll take the convention that $XY$ means "apply the permutation $X$ to the elements, and then apply the permutation $Y$)

The algorithm is straight-forward; we know that $XY = ZX$, so:

We pick an arbitrary element of the permutation $a$ and assume that $X(a) = b$ (where $b$ is a previously output of $X$).  We then can deduce the value $XY(a) = d$ (where $d = Y(b)$).  In addition, we have $Z(a) = c$ (for some element $c$), and so we can then deduce $X(c) = d$.

Assuming that $c, d$ are previously unknown inputs/outputs of $X$, we reiterate the same logic, which will give us another pair $X(e) = f$.

We keep on doing this until it gives us a pair that we've seen before, or it gives an inconsistent pair (that is, it assigned the same $X(g)$ value to two different outputs, or it gives us a set $g \ne h, i$ with $X(g) = X(h) = i$

If it gives us an inconsistent pair, we drop back to the previous assumption that $X(a) = b$, and modify $b$, and restart our computation from there.

If it gives us a pair that we've seen before, and there are still unassigned inputs/outputs to $X$, we restart at the beginning, arbitrarily selecting a previously unassigned input/output pair.

This won't give a unique value of $X$; that's because there are multiple solutions, and this will pick one arbitrarily.

Update: I just wrote a quick (and fairly suboptimal) C program to do this; it could find a conjugate (where one existed) given two permutations over 10,000 elements in under a second...


KDF for generating RSA and ECC keys from a 2048 bit secret Do KDFs exist for generating RSA and ECC keys from a 2048-bit random secret?

Rather no. There is no standard construction going by the name Key Derivation Function aimed at generating public/private key pairs. Traditionally, especially for RSA, how to generate a key pair is left at the discretion of the implementation, rather than made per a specific deterministic process. The usual name is Key Generation. And it's usually stated as a randomized algorithm, rather than as a function.
For ECC per Sec1, it is straightforward to define such KDF. The private key is an integer $d$ in range $[1,n-1]$ where $n$ is the fixed, public order of a generator on a curve. Thus we could take the 2048-bit secret¹ $s$, and turn it to the private key by applying $d\gets(s\bmod(n-1))+1$; then compute the public key by applying $Q\gets d\,G$ using point multiplication. Since in practice $n\le2^{800}$, the bias on $d$ is negligible if the 2048-bit $s$ is uniformly random.
For RSA, that's less easy. We need to specify a Cryptographically Secure Pseudo-Random Number Generator, seed it with the 2048-bit secret¹ $s$, and generate the RSA key per some precisely agreed-upon process. FIPS 186-4 appendix B.3.2 is next to being precise enough. Also, beware that it is hard to secure such computations from side-channel and fault attacks.

¹ Or a derivative $s$ of that secret by a symmetric KDF.