diff --git a/rpm-4.13.0-non-ASCII-keys.patch b/rpm-4.13.0-non-ASCII-keys.patch
new file mode 100644
index 0000000..284b734
--- /dev/null
+++ b/rpm-4.13.0-non-ASCII-keys.patch
@@ -0,0 +1,31 @@
+From 258e3065687c9e6b53b6f2b6c7fa6c5694508791 Mon Sep 17 00:00:00 2001
+From: Lubos Kardos <lkardos@redhat.com>
+Date: Mon, 23 May 2016 10:19:39 +0200
+Subject: [PATCH] Fix signing with non-ASCII uid keys (rhbz:1243963)
+
+Removed setting LC_ALL to "C" because since commit [1] the gpg program
+gets password by yourself from terminal so there is no sense in
+setting LC_ALL to "C" if the terminal settings is e. g. UTF-8. That was
+only confusing gpg program and it was not able to properly get and
+display non-ASCII characters.
+
+[1] 0bce5fcf270711a2e077fba0fb7c5979ea007eb5
+---
+ sign/rpmgensig.c | 1 -
+ 1 file changed, 1 deletion(-)
+
+diff --git a/sign/rpmgensig.c b/sign/rpmgensig.c
+index 2310f14..321d19c 100644
+--- a/sign/rpmgensig.c
++++ b/sign/rpmgensig.c
+@@ -267,7 +267,6 @@ static int runGPG(sigTarget sigt, const char *sigfile)
+ 
+ 	if (gpg_path && *gpg_path != '\0')
+ 	    (void) setenv("GNUPGHOME", gpg_path, 1);
+-	(void) setenv("LC_ALL", "C", 1);
+ 
+ 	unsetenv("MALLOC_CHECK_");
+ 	cmd = rpmExpand("%{?__gpg_sign_cmd}", NULL);
+-- 
+1.9.3
+
diff --git a/rpm.spec b/rpm.spec
index e5baf0f..9f50476 100644
--- a/rpm.spec
+++ b/rpm.spec
@@ -29,7 +29,7 @@
 Summary: The RPM package management system
 Name: rpm
 Version: %{rpmver}
-Release: %{?snapver:0.%{snapver}.}35%{?dist}
+Release: %{?snapver:0.%{snapver}.}36%{?dist}
 Group: System Environment/Base
 Url: http://www.rpm.org/
 Source0: http://rpm.org/releases/rpm-4.12.x/%{name}-%{srcver}.tar.bz2
@@ -83,6 +83,7 @@ Patch127: rpm-4.13.0-rpmtd-out-of-bounds.patch
 Patch128: rpm-4.13.0-stringFormat-sigsegv.patch
 Patch129: rpm-4.13.0-filter-unversioned.patch
 Patch130: rpm-4.13.0-armv7hl-isa.patch
+Patch131: rpm-4.13.0-non-ASCII-keys.patch
 
 # These are not yet upstream
 Patch302: rpm-4.7.1-geode-i686.patch
@@ -594,6 +595,9 @@ exit 0
 %doc doc/librpm/html/*
 
 %changelog
+* Mon May 23 2016 Lubos Kardos <lkardos@redhat.com> 4.13.0-0.rc1.36
+- Fix signing with non-ASCII uid keys (#1243963)
+
 * Thu May 19 2016 Lubos Kardos <lkardos@redhat.com> 4.13.0-0.rc1.35
 - Use armv7hl isa for all armhfp (armv7h*l) arches (#1326871)