1 Тема від 221VOLT

  • 221VOLT
  • 221VOLT
  • ♥ pattern matching
  • Поза форумом
  • Звідки: Львів
  • Дата реєстрації: 26.09.2015
  • Повідомлень: 2 720
    • Репутація: 1876

Тема: Haskell && Bitcoin Elliptic Curve Crypto

пробував розібратись як "вручну" рахувати ті точки на еліптичних кривих
( Elliptic Curve Crypto в Bitcoin -- це вичислення публічного ключа з приватного ),
рішення-"костиль" для свого кривого коду наче знайшов,

і все ж хочеться уточнити чому у певний момент працювало "криво" --
1 -- я не (повністю) догнав як готувати хаскель ?
2 -- я не (повністю) догнав формулу додавання точок ?
3 -- я не (повністю) догнав модульну арифметику/модульну інверсію ?
4 -- я не догнав ще щось ???

хочу критики, варіант рефакторинга коду etc


[:} переходимо до суті "кривизни"


для Private_Key "0x59" все вичислялось ок,
для "0x5A" -- на 5-му кроці було щось не те...

консоль в хаскелі з демонстрацією кривизни

▼Прихований текст
ghci> test_Pub "5A" 1
"C6047F9441ED7D6D3045406E95C07CD85C778E4B8CEF3CA7ABAC09B95C709EE5 1AE168FEA63DC339A3C58419466CEAEEF7F632653266D0E1236431A950CFE52A"
ghci> test_Pub "5A" 2
"2F8BDE4D1A07209355B4A7250A5C5128E88B84BDDC619AB7CBA8D569B240EFE4 D8AC222636E5E3D6D4DBA9DDA6C9C426F788271BAB0D6840DCA87D3AA6AC62D6"
ghci> test_Pub "5A" 3
"774AE7F858A9411E5EF4246B70C65AAC5649980BE5C17891BBEC17895DA008CB D984A032EB6B5E190243DD56D7B7B365372DB1E2DFF9D6A8301D74C9C953C61B"
ghci> test_Pub "5A" 4
"421F5FC9A21065445C96FDB91C0C1E2F2431741C72713B4B99DDCB316F31E9FC 2B90F16D11DABDB616F6DB7E225D1E14743034B37B223115DB20717AD1CD6781"
ghci> test_Pub "5A" 5
"293D4129D2F5E8B5564A88F71B56456B9CA2830E749ABCC4C5A20DFA35849D32 24D4568D7FD2BA02D21345472F67573D5E2E0CB89E3930D9E786583440F900C7"
ghci> test_Pub "5A" 6
"F169B7D1930AA8DF79CA16C8DF68E789844AEC013A883D99EEE51E8B58D1C82A 77A081CBDCCFA4E22CC8D96BF183A3A2368B94C4829C0DC6CE984515ACDFCBD7"

ghci> test_Pub "59" 1
"C6047F9441ED7D6D3045406E95C07CD85C778E4B8CEF3CA7ABAC09B95C709EE5 1AE168FEA63DC339A3C58419466CEAEEF7F632653266D0E1236431A950CFE52A"
ghci> test_Pub "59" 2
"2F8BDE4D1A07209355B4A7250A5C5128E88B84BDDC619AB7CBA8D569B240EFE4 D8AC222636E5E3D6D4DBA9DDA6C9C426F788271BAB0D6840DCA87D3AA6AC62D6"
ghci> test_Pub "59" 3
"774AE7F858A9411E5EF4246B70C65AAC5649980BE5C17891BBEC17895DA008CB D984A032EB6B5E190243DD56D7B7B365372DB1E2DFF9D6A8301D74C9C953C61B"
ghci> test_Pub "59" 4
"421F5FC9A21065445C96FDB91C0C1E2F2431741C72713B4B99DDCB316F31E9FC 2B90F16D11DABDB616F6DB7E225D1E14743034B37B223115DB20717AD1CD6781"
ghci> test_Pub "59" 5
"5D045857332D5B9E541514731622AF8D60C180165D971A61E06B70A9B3834765 DB2BA972802D45FD2DECBAB8D098A8C2A1D1F34761C6CF261879A7CABF06FB68"
ghci> test_Pub "59" 6
"D3CC30AD6B483E4BC79CE2C9DD8BC54993E947EB8DF787B442943D3F7B527EAF 8B378A22D827278D89C5E9BE8F9508AE3C2AD46290358630AFB34DB04EEDE0A4"

повинно бути

▼Прихований текст
//"59"
0
c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5
1ae168fea63dc339a3c58419466ceaeef7f632653266d0e1236431a950cfe52a
1
2f8bde4d1a07209355b4a7250a5c5128e88b84bddc619ab7cba8d569b240efe4
d8ac222636e5e3d6d4dba9dda6c9c426f788271bab0d6840dca87d3aa6ac62d6
1
774ae7f858a9411e5ef4246b70c65aac5649980be5c17891bbec17895da008cb
d984a032eb6b5e190243dd56d7b7b365372db1e2dff9d6a8301d74c9c953c61b
0
421f5fc9a21065445c96fdb91c0c1e2f2431741c72713b4b99ddcb316f31e9fc
2b90f16d11dabdb616f6db7e225d1e14743034b37b223115db20717ad1cd6781
0
5d045857332d5b9e541514731622af8d60c180165d971a61e06b70a9b3834765
db2ba972802d45fd2decbab8d098a8c2a1d1f34761c6cf261879a7cabf06fb68
1
d3cc30ad6b483e4bc79ce2c9dd8bc54993e947eb8df787b442943d3f7b527eaf
8b378a22d827278d89c5e9be8f9508ae3c2ad46290358630afb34db04eede0a4

//"5A"
0
c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5
1ae168fea63dc339a3c58419466ceaeef7f632653266d0e1236431a950cfe52a
1
2f8bde4d1a07209355b4a7250a5c5128e88b84bddc619ab7cba8d569b240efe4
d8ac222636e5e3d6d4dba9dda6c9c426f788271bab0d6840dca87d3aa6ac62d6
1
774ae7f858a9411e5ef4246b70c65aac5649980be5c17891bbec17895da008cb
d984a032eb6b5e190243dd56d7b7b365372db1e2dff9d6a8301d74c9c953c61b
0
421f5fc9a21065445c96fdb91c0c1e2f2431741c72713b4b99ddcb316f31e9fc
2b90f16d11dabdb616f6db7e225d1e14743034b37b223115db20717ad1cd6781
1
49370a4b5f43412ea25f514e8ecdad05266115e4a7ecb1387231808f8b45963
758f3f41afd6ed428b3081b0512fd62a54c3f3afbb5b6764b653052a12949c9a
0
eb49fd9f510469f4fe540e4b0664410f216cbbc90d97aed62af2e606110cc919
6e638df7a9105bbc34db14f93706891d5d6406cbfcd76e174c481324a6c8912b

тикаючи паличкою шляхом досліджень я виявив наступне:
1 -- функція doublePoint працює ок
2 -- функція addPoints -- не завжди

код цих функцій

▼Прихований текст
doublePoint :: [Integer] -> [Integer]
--doublePoint :: [Integer] -> [String]
--doublePoint (x:y:[]) = [integer2hex x2, integer2hex y2]
doublePoint (x:y:[]) = [mod x2 p, mod y2 p]
  where s0 = modInv (mod (2 * y) p) p
        s = mod (s0 * 3 * x * x) p
        x2 = mod (s * s - 2 * x) p
        y2 = mod ( - (s * (x2 - x) + y)) p


addPoints :: [Integer] -> [Integer] -> [Integer]
--addPoints :: [Integer] -> [Integer] -> [String]
--addPoints (x1:y1:[]) (x2:y2:[]) = [integer2hex x3, integer2hex y3]
addPoints (x1:y1:[]) (x2:y2:[]) = [x3, y3]
  where s = (y1 - y2) * (modInv (x1 - x2) p)
        x3 = mod ( s * s - x1 - x2) p
        y3 = mod ( s * (x1 - x3) - y1) p

досліджуючи далі, стало зрозуміло --
addPoints має повертати

[2069755349039566255304036353648839232649715781170511813011535420394543798627,
53173698995439924366951845531266805314230463309822098990695656330917108292762]

для наступного варіанту застосування

gX = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
gY = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
n1 = 42072772011086351294328511389423850314698152445154323541536957340534349973349
n2 = 99133657745585934968186133288050721248258413615930917407282740640761199917928
addPoints [n1, n2] [gX, gY]

повертає ж наступне

[18653054203952500459663754724095523212321228766708646322420439306985367969074,
16658431491730260455384851720637186605011571049709646632174843367147634753735]

і якщо я перепишу функцію addPoints наступним чином --

▼Прихований текст
addPoints :: [Integer] -> [Integer] -> [Integer]
--addPoints :: [Integer] -> [Integer] -> [String]
--addPoints (x1:y1:[]) (x2:y2:[]) = [integer2hex x3, integer2hex y3]
addPoints (x1:y1:[]) (x2:y2:[]) = [x3, y3]
  where s = (y2 - y1) * (modInv (x2 - x1) p)
        x3 = mod ( s * s - x1 - x2) p
        y3 = mod (s * (x1 - x3) - y1) p

то для суми двох точок вище -- результат повертатиметься вірний,
та буде помилка з попередніми додаваннями, де раніше повертався правильний результат!

в результаті у мене ок працює отакий костиль

▼Прихований текст
addPoints :: [Integer] -> [Integer] -> [Integer]
--addPoints :: [Integer] -> [Integer] -> [String]
--addPoints (x1:y1:[]) (x2:y2:[]) = [integer2hex x3, integer2hex y3]
addPoints (x1:y1:[]) (x2:y2:[]) = [x3, y3]
  where s
--         | y2 > y1 = (y2 - y1) * (modInv (x2 - x1) p)
--         | y1 > y2 = (y1 - y2) * (modInv (x1 - x2) p)
--         | y1 > y2 = (y2 - y1) * (modInv (x2 - x1) p)
--         | y2 > y1 = (y1 - y2) * (modInv (x1 - x2) p)
         | x2 > x1 = (y2 - y1) * (modInv (x2 - x1) p)
         | x1 > x2 = (y1 - y2) * (modInv (x1 - x2) p)
--         | x1 > x2 = (y2 - y1) * (modInv (x2 - x1) p)
--         | x2 > x1 = (y1 - y2) * (modInv (x1 - x2) p)
        x3 = mod ( s * s - x1 - x2) p
        y3 = mod ( s * (x1 - x3) - y1) p

загалом як я зрозумів - існує приблизно 3 способи порахувати публічний ключ з приватного,
і я навчився рахувати в 1й спосіб  8) , маю код 2го способу  8) ,
залишилось догнати як рахувати 3м способом  *CRAZY*

+ трішки догнав що таке модульна арифметика  [:}

код в результаті
https://gist.github.com/221V/b1d9ab83a2 … 954ec2c5aa

використані матеріали --
http://gobittest.appspot.com/Address -- перевірки
формули --
https://github.com/BitcoinPHP/BitcoinEC … nECDSA.php
https://gist.github.com/nlitsme/c9031c7b9bf6bb009e5a
https://bitcoin.stackexchange.com/quest … -ecc-curve
https://bitcointalk.org/index.php?topic … sg26195945
http://royalforkblog.github.io/2014/09/04/ecc/
https://hackernoon.com/eliptic-curve-cr … eb1e934dc5
https://hackernoon.com/elliptic-curve-c … 8508d40a88
https://hackernoon.com/elliptic-curve-c … f6cb9916d7
https://www.reddit.com/r/Bitcoin/commen … ey_from_a/
https://bitcoin.stackexchange.com/quest … rivate-key

Подякували: Betterthanyou1

221VOLT вебсайт

2 Відповідь від 221VOLT Востаннє редагувалося 221VOLT (28.02.2020 22:56:04)

  • 221VOLT
  • 221VOLT
  • ♥ pattern matching
  • Поза форумом
  • Звідки: Львів
  • Дата реєстрації: 26.09.2015
  • Повідомлень: 2 720
    • Репутація: 1876

Re: Haskell && Bitcoin Elliptic Curve Crypto

дивлюся я на

▼en, link

і розумію, що загалом уже все зрозуміло:

є крива, з точками якої працюємо,
крива лежить в обмеженому полі
( не на декартових координатах з безкінечністю в максимальних(мінімальних) значеннях X та Y,
а з максимальним значенням
p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
і це є запис великого десяткового числа в 16-му форматі ),

при виході за це значення відбувається
x mod p,
тобто, на прикладі p = 5, x1 = 3, x2 = 4
x = x1 + x2 = 7 mod 5 = 2
(формула скалярного додавання точок трохи складніша,
вище було наведено формулу у вигляді робочого коду),

при цьому точки, які ми додаємо --
це біти нашого приватного 256-бітного ключа:
приватний ключ ...1010 -> публічний ключ = G1 + G3
(0 ігноруємо, 1 -- додаємо точку),

відповідно ми отримує публічний ключ,
який складається з двох значень: x та y,

оскільки існує більше ніж 1 спосіб записати публічний ключ,
ми можемо зустріти такі значення:
04...
03...
02...

перший запис -- це "нестиснутий" публічний ключ,
який відповідає запису "04" ++ x ++ y,
2й та 3й записи -- це "стиснутий" публічний ключ,
що відповідає запису "03" ++ x чи "02" ++ x,
оскільки у функції біткоїна (за вийнятком точки перетину осі x)
кожному x відповідає два y (відповідно ),
тут префікс залежить від того, чи y є парним числом ("02"), чи непарним ("03")


:)
це є отримання публічного ключа з приватного,
загалом все зрозуміло, все просто :)


--------------------------

та є один момент, який я не розумію:

▼Прихований текст

Finally the order n of G and the cofactor are:

    n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
    h = 01

хтось може пояснити, що це таке(це значення n, та h), і навіщо це,
доступно-зрозуміло, та українською?
дякую!

Подякували: NaharD, leofun012

221VOLT вебсайт