Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I'd be a noob in cryptography but reading up a little on RSA, I do get some understanding and I want to specifically resolve this issue.

UPDATED

Lets say we have the following values in place:

KEYSIZE = 512  
HASHSIZE =  sha.digestsize*8 
digest = some SHA 512 function

We calculate the pub_key,pvt_key e,d via n = p*q and totient function phy = (p-1)*(q-1) in effect getting 1 < e < tot_func and we get d=e mod tot_func

PS : pub and pvt keys are created as an RSA_function(KEYSIZE)

Implementing an RSA scheme, we have a token m

Now

c(m) = m^e mod n

Decrypting it would be:

m = c^d mod n

PS: m is a token number (instead of padding a m=token hash, converted from some m=f(M)) To be specific:

m = convert_str_to_long(sha_digest(M))

M itself is of random HASHSIZE bits


Chaumian Blinding

I want to know where I'm going wrong with this. Given the same scheme as above for token id m, However I want to be clear with a Chaum's blinding scheme and implement that instead.

we have n,p,q,d,e,m

To blind quoting from Blinding

For example, in RSA blinding involves computing the blinding operation E(x) = x*r^e mod N, where r is a random integer between 1 and N and relatively prime to N (i.e. gcd(r, N) = 1), x is the ciphertext, e is the public RSA exponent and N is the RSA modulus. As usual, the decryption function f(z) = zd mod N is applied thus giving f(E(x)) = x^d*r^ed mod N = x^d*r mod N. Finally it is unblinded using the function D(z) = zr^−1 mod N. Since D(f(E(x))) = x^d mod N, this is indeed an RSA decryption. However, when decrypting in this manner, an adversary who is able to measure time taken by this operation would not be able to make use of this information (by applying timing attacks RSA is known to be vulnerable to) as she does not know the constant r and hence has no knowledge of the real input fed to the RSA primitives.

Blind requires creating a blinding factor,r.

while 1:
    r = random.getrandbits(KEYSIZE-1)
    Verify that GCD(r, n) ==1
    if gcd(r, n)==1: break;
  • Create a blinding factor, r
  • Create blinded_token = m * (r^e % n)

Questions:

  • What the heck do you do after that? Decrypt > Unblind Or Unblind > Decrypt to recover token m?
  • Also, if you want to sign the blinded_token do you Sign > Decrypt > Unblind OR Sign > Unblind > Decrypt ?
  • How do you Unblind actually based on above blinding?

My goal is to recover back m.

Please do tell me if you need some more info. I need this asap.

Thanks in advance!

UPDATE I would like to credit both Rick and the OP here in my work regarding this. I got the solution finally.

share|improve this question

1 Answer 1

up vote 0 down vote accepted

A much better way to choose r is

while 1:
    s = random.getrandbits(KEYSIZE+privacyparameter)
    r = 1+(s%(n-1))
    if gcd(r,n) == 1: break;

.


privacyparameter is chosen by the blinder.
If $\:$ gcd(m,n) = 1 $\:$ then the statistical distance between the distribution of blinded_token and
the uniform distribution on units mod n is less $\:$ n/((2^(KEYSIZE+privacyparameter+1))-(2*n)) $\;$.
The signer does not need to know or care what that value is.

It's much better to create $\;\;$ blinded_token $\:$=$\:$ (m * (r^e % n)) % n $\;\;$,
so that the size of the output won't leak much information about m.

The signer computes $\:$ (blinded_token)^d % n $\:$ and sends that to the blinder. $\:$ If the signer instead
signed or decrypted the token in the standard way, then the blind signature scheme wouldn't work.

If $\;\;$ (signers_response)^e % n $\:$=$\:$ blinded_token $\;\;$ then output
((signers_response)*modinv(r,n)) % n $\;$ as the unblinded signature, else reject.


There are two further subtleties for this blind signature scheme:

gcd(blinded_token,n) = 1 $\;$ if and only if $\;$ gcd(m,n) = 1
However, as alluded to in the one of the OP's comments to this answer,
the hash can to chosen to guarantee that $\:$ gcd(m,n) = 1 $\;$.
(So, hopefully, "sha_digest" is something that does so, rather than just one of the SHA functions.)

Also, if the RSA function does not define a permutation over $\mathbb{Z}_n^*$, then blindness
does not necessarily hold even if all relevant values of m satisfy gcd(m,n) = 1.

share|improve this answer
    
what's the privacy parameter in random.getrandbits(KEYSIZE+privacyparameter) ? pvt key? –  user2290820 Apr 14 at 14:09
    
How do you sign after blinding? sign = Blinded_message**d? I mean Blinded_message number is long long long.. and equally for d! multiplying them would take gazillion years. What am I doing wrong or what do I need to do now? –  user2290820 Apr 14 at 15:17
    
How do you sign after blinding? sign = Blinded_message**d? I mean Blinded_message number is long long long.. and equally for d! multiplying them would take gazillion years. What am I doing wrong or what do I need to do now? –  user2290820 Apr 14 at 15:28
    
gcd(m,n) = 1 in my case –  user2290820 Apr 14 at 15:32
    
see i need to know how "privacyparameter is chosen by the blinder". how does one create the privacy parameter? Also how can signing r**d where r and d are enormous be possible? –  user2290820 Apr 14 at 19:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.