If the working certificate also use the "new format" (BEGIN PRIVATE KEY), then the current hypothesis seems insufficient. However, could you still see what happens if you convert the key to the "old format" and use the result, as suggested by andrew finkenstadt's post?

openssl rsa -in jenkins.example.net.key -out jenkins_new.example.net.key

However, (I guess) Jenkins shouldn't contain its own code to parse keys anyway, it should at best just integrate some third-party library for it (hoping there's a library you can use without too much expertise).

For now, fixing docs seems more urgent.

It works with the old key format! I have converted the key on centos 5 box with the following openssl version

# openssl version
OpenSSL 0.9.8e-fips-rhel5 01 Jul 2008

But as before it has very low result on ssl labs. So the question - is it possible to enable Forward Secrecy, disable RC4 and enable support of strong Diffie-Hellman (DH) key exchange (1024+) ? Or the only way is for using some sort of reverse proxy such as nginx/haproxy/apache?

alex_hha Good question, but that belongs to a separate bug.

Googling leads to https://issues.jenkins-ci.org/browse/JENKINS-23925, but even after the "workaround" there (switching away from Java 6) RC4 looks enabled. Jenkins's default servlet container doesn't seem to document extensive SSL configuration support (see http://winstone.sourceforge.net/#https).
After some googling, I'd guess that either changing servlet container (to some with good HTTPS support) or reverse proxying seems a better idea, at least because it's done often and well documented — I couldn't even find how to disable RC4 with Jenkins, while I've run into how to configure nginx without looking for it.
(Again, I'm just another user bitten from the issue).

I think it would be great if someone from developers will say anything

P.S.
My jenkins ships with JAVA_VERSION="1.8.0_20".

even after the "workaround" there (switching away from Java 6) RC4 looks enabled.

If the problem is not just outdated Java (remember that Java 7 already is old as well, should to be newest version of that), please reopen. It shouldn't be too difficult to implement.

So it looks like for Java you can just configure that rather than your application.

http://docs.oracle.com/javase/7/docs/technotes/guides/security/jsse/JSSERefGuide.html#DisabledAlgorithms
Here's a guide for a different application: http://www.papercut.com/kb/Main/SSLCipherConfiguration

Do these help?

OMG, the "bloody" java

I will try it and will let you know

P.S.
in tomcat for e.g. it's configuring in very simple way

<Connector port="443" protocol="org.apache.coyote.http11.Http11AprProtocol"
   scheme="https"
   secure="true"
   clientAuth="false"
   useBodyEncodingForURI="true"

   SSLEnabled="true"
   SSLHonorCipherOrder="true"
   SSLDisableCompression="true"
   SSLCertificateFile="/etc/pki/jira/jira.example.net.crt"
   SSLCertificateKeyFile="/etc/pki/jira/jira.example.net.key"
   SSLCACertificateFile="/etc/pki/jira/ca.pem"
   SSLCertificateChainFile="/etc/pki/jira/sub.class1.server.ca.pem"
   SSLCipherSuite="kEECDH+AES128:kEECDH:kEDH:-3DES:kRSA+AES128:kEDH+3DES:DES-CBC3-SHA:!RC4:!aNULL:!eNULL:!MD5:!EXPORT:!LOW:!SEED:!CAMELLIA:!IDEA:!PSK:!SRP:!SSLv2"
   SSLProtocol="TLSv1+TLSv1.1+TLSv1.2"
/>

I'm using the official jenkins docker container to run my jenkins master. Just tried add key and certificate and I'm getting what appears to be the same error.
Would using openssl to convert the key or cert to a different format help?
{{SEVERE: Container startup failed
java.io.IOException: Failed to start a listener: winstone.HttpsConnectorFactory
at winstone.Launcher.spawnListener(Launcher.java:209)
at winstone.Launcher.<init>(Launcher.java:149)
at winstone.Launcher.main(Launcher.java:354)
at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
at java.lang.reflect.Method.invoke(Method.java:497)
at Main._main(Main.java:293)
at Main.main(Main.java:98)
Caused by: java.io.IOException: DerValue.getBigInteger, not an int 48
at sun.security.util.DerValue.getBigInteger(DerValue.java:511)
at winstone.HttpsConnectorFactory.readPEMRSAPrivateKey(HttpsConnectorFactory.java:173)
at winstone.HttpsConnectorFactory.start(HttpsConnectorFactory.java:89)
at winstone.Launcher.spawnListener(Launcher.java:207)
... 8 more
}}

solved with jenkins docker container by converting everything to a keystore

first added a password to my key
openssl rsa -des3 -in key.pem -out key.encrypted.pem

then converted to pkcs12
openssl pkcs12 -inkey key.encrypted.pem -in cert.pem -export -out keys.encrypted.pkcs12

then created a keystore (password for keystore should be same as password for key)
keytool -importkeystore -srckeystore keys.encrypted.pkcs12 -srcstoretype pkcs12 -destkeystore keystore

then updated Dockerfile to include keystore and a reference to it in JENKINS_OPTS
{{FROM jenkins
USER root
RUN apt-get update && apt-get install -y jq
USER jenkins
COPY keystore /var/lib/jenkins/keystore
ENV JENKINS_OPTS --httpPort=8080 --httpsPort=8443 --httpsKeyStore=/var/lib/jenkins/keystore --httpsKeyStorePassword=whateverpasswordyouspecified
EXPOSE 8443}}
.

The problem is that Jenkins expects a RSA key, not a private key

Convert /var/lib/jenkins/cert/cci-jenkins.key into a plain RSA key:

cp /var/lib/jenkins/cert/cci-jenkins.key /var/lib/jenkins/cert/cci-jenkins.key.full
openssl rsa -in  /var/lib/jenkins/cert/cci-jenkins.key.full -out /var/lib/jenkins/cert/cci-jenkins.key

http://stackoverflow.com/questions/17733536/how-to-convert-a-private-key-to-an-rsa-private-key