How to verify the validity of a transaction

[redPanda]

I want to verify the validity of a transaction

Signing a tx

In order to sign a tx, I need:
    - <privKey>, Random Number = RN and the hash of tx = txHash

To sign the tx I must publish the <pubKey> = <privKey> * G = (X, Y)
where G is the Generator point

and I also must publish a signature = <sig> = (r,s)
where s is a random number:
    generate a random number RN, and compute s = RNx like this:
    RN * G = (RNx, RNy)
and r is a signature factor built with txHash, RNx, <privKey> and RN

then the signature script <sigScript> = <sig> + <PubKey> = (r,s) + (X,Y)

Verify a tx

If I have all infos r, s = RNx, RNy, X, Y, I can sign a tx and verify its validity with my script

BUT in a Bitcoin transaction sometimes X and Y are given: 04 X Y
and sometimes only X is given: 02 X or 03 X

also only s = RNx is given and not RNy.

So in order to verify a tx, I need to compute Y and RNy
Question 1) is there a way to do it without Y and/or RNy ?

question 2) There is a simplify algorithm to find Y when
computing square roots mod p when p = 3 (mod 4).
I checked that this condition is satisfied with the p used in Bitcoin.
Am I correct ? Can I use this algorithm ?

if p = 3 (mod 4) the solution of y^2 = x^3 + 4 = a (mod p)
has the form y = a^(k+1)
proof: if p = 4k+3 then set y=a^(k+1) mod p then
y^2 = a^(2k+2) = a^(2k+1) a = a^((p-1)/2) a = a (mod p)
by Euler's Criterion. So y = a^(k+1) is a solution.

Question 3) Is there a risk of collision when finding Y or RNy?
In a simple example (http://www.royalforkblog.com/2014/09/04/ecc/)
p = 29 and privKey = 7 => 7 * G = (17,9)
If I only have X = 17 I have 2 choices for Y: (17,9) or (17,20)

Thanks

[1714781162]

1714781162

[1714781162]

1714781162

[1714781162]

1714781162

[1714781162]

1714781162

[DannyHamilton]

- snip -
BUT in a Bitcoin transaction sometimes X and Y are given: 04 X Y
and sometimes only X is given: 02 X or 03 X
- snip -

Exactly.  And the 02 or 03 that you've mentioned is there because Y could have two different values.  The 02 or 03 let you know which of the two values you should be using.

If I only have X = 17 I have 2 choices for Y: (17,9) or (17,20)

Fortunately you shouldn't only have X = 17.

You should either have
02 X = 17
or
03 X = 17

[redPanda]

Thanks a lot 
and what about the random number RNy from s = RNx ?

[johoe]

You don't need RNy to check validity.

Compute txHash/s * G + r/s * (X,Y), which should give you RN * G = (RNx, RNy).  Then just check if r = RNX.

EDIT: Your notation is somewhat non-standard.  RN is usually called k.  What I called r,s above is the ECDSA signature. r is RNx, and s is (txHash + r*d)/k, where d is the private key. It seems that you swapped r and s.

[redPanda]

It seems that you swapped r and s

Yes, you're right, I think, my error came from http://www.royalforkblog.com/2014/09/04/ecc/ (with small numbers)
where they give "signature = 22,13" (with 22 = s and 13 = r: reverse order). I should have checked twice.
And thanks a lot for reading my long question.